綺麗な方法が分からなかったから,問題文にある通りグラフで考えた. DFSして,連結成分ごとに,辿り着いたvertices を手に入れて, 大きい順に出力.
公式解説
公式解説を見て,while 文で実装.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m;
cin >> n >> m;
vll a(m);
cinv(a);
vvll to(n);
rep(i,m){
a[i]--;
ll x = a[i];
ll y = a[i]+1;
to[x].push_back(y);
to[y].push_back(x);
}
vll vis(n);
ll cnt = 0;
vll v;
if(vis[cu]){
return ;
}
vis[cu] = true;
v.push_back(cu);
f(f, ne, cu);
}
};
rep(i,n) if(!vis[i]){
v = vll();
dfs(dfs, i);
sort(all(v), greater<ll>());
for(auto x: v){
cout << x+1 << " ";
}
}
return 0;
}
int main() {
ll n, m;
cin >> n >> m;
vll a(m);
cinv(a);
rep(i,m){
a[i]--;
}
a.push_back(-1);
ll l = 0 , r = 0;
ll k = 0;
while(l < n){
r = l;
if(a[k] == r){
while(a[k+1]==a[k]+1) k++;
r = a[k] + 1;
k++;
}
dsrep(i,r+1, l) cout << i+1 << " ";
l = r+1;
}
return 0;
}
int main() {
ll n, m;
cin >> n >> m;
vll a(m); cinv(a);
rep(i,m) --a[i];
a.push_back(-1);
vll ans;
vll vis(n);
rep(i,n) if(!vis[i]){
if(in(i,a)){
vll t;
ll k = 0;
rep(j,m){
if(a[j] == i){
k = j;
break;
}
}
while(true){
t.push_back(a[k]);
vis[a[k]] = true;
k++;
if(a[k] != a[k-1]+1) break;
}
t.push_back(t.back()+1);
vis[t.back()] = true;
reverse(all(t));
ans.insert(ans.end(), all(t));
}else{
ans.push_back(i);
vis[i] = true;
}
}
for(auto x: ans){
cout << x+1 << " ";
}
return 0;
}