問題
http://codeforces.com/contest/698/problem/B
n要素の順列 pi を考える。
この順列は以下の要件をみたすとき valid とされる
- 頂点iと頂点piに辺が作られる
- 木の根は pi = i となっている(ただ一つ)
- この条件で辺を作ると、n要素の木ができあがる
与えられた順列を valid にするために必要最小限の改変回数と改変後の数列を出力せよ
2 <= n <= 2*10^5
考察
1. 探索するようなタイプでもない
2. 今回はnの制約がわりかしきついので、根を全通り試すようなことはなさそう
3. 全通りというか、候補が幾つか決まっていて、そこから全通り試すというのもなさそう
4. 実験してある程度考察が必要???
5. 実験を頑張るとループになるような辺は変える必要があるが分かる
6. 辺の先をどこに変えるかだが、候補を全通り試すような余裕はなさそう…
7. 根に付け替えれば必ずループにならない
8. あとは根の選択
9. 最初の順列の中で pi = i であるもののどれかが根になる
10. どれを根にするか考えるが、ここでも候補を全通り試すような余裕はなさそう…
11. どれでもいい!!(俺は最初に見つけたやつにしました)
12. もし pi = i であるものが無ければ、ループになるような辺から1つどれでもいいので選びます
13. というようなことをやればいいので、pi=iとなるやつとループになりそうなやつをメモっておいて、あとで処理してやればいいです
14. ループになるかの判定はUnion-Findあたりを使ってやるとお手軽ですね
実装
http://codeforces.com/contest/698/submission/19258119
template<int um> class UF { // from kmjp public: vector<int> par; UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; } int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); } void operator()(int x, int y) { x = operator[](x); y = operator[](y); if (x != y) par[x] = y; } }; //----------------------------------------------------------------- int n; int a[201010]; //----------------------------------------------------------------- int main() { scanf("%d", &n); rep(i, 0, n) scanf("%d", &a[i]), a[i]--; UF<201010> uf; vector<int> roots, loops; rep(i, 0, n) { if (a[i] == i) { roots.push_back(i); continue; } if (uf[i] == uf[a[i]]) loops.push_back(i); else uf(i, a[i]); } int ans = 0; if (roots.size() == 0) { if (loops.size() != 0) { int root = loops[0]; a[root] = root; ans++; rep(i, 1, loops.size()) a[loops[i]] = root, ans++; } } else { int root = roots[0]; a[root] = root; rep(i, 1, roots.size()) a[roots[i]] = root, ans++; rep(i, 0, loops.size()) a[loops[i]] = root, ans++; } printf("%d\n", ans); rep(i, 0, n) printf("%d ", a[i] + 1); printf("\n"); }