はまやんはまやんはまやん

hamayanhamayan's blog

Fix a Tree [Codeforces 363 : Div2 D, Div1 B]

問題

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");
}