[Codeforces] 698B. Fix a Tree

題目連結:http://codeforces.com/problemset/problem/698/B

---

一開始完全沒想法，被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy，就先判斷一下有沒有原本就有可以當根的點，有的話就把他當根，接下來再掃一遍，看看有沒有人會構成環，有的話就直接把他接到根上面，此外，若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define FF first
#define SS second
const int N = 200000 + 5;

class DJS{
	private:
		vector<int> arr;
	public:
		void init(int n){
			arr.resize(n);
			for(int i=0;i<n;i++) arr[i]=i;
		}
		int query(int x){
			if(arr[x]!=x) arr[x] = query(arr[x]);
			return arr[x];
		}
		void merge(int a, int b){
			arr[query(a)]=arr[query(b)];
		}
} djs;

int arr[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, ans = 0, root = -1; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		if(arr[i]==i and root==-1) root=i;
	}
	djs.init(n+1);
	for(int i=1;i<=n;i++){
		int x = arr[i];
		if(x == root) continue;
		if(djs.query(x) == djs.query(i)){
			if(root == -1){
				root = i;
				if(x!=i){
					x=i;
					ans++;
				}
			}else{
				djs.merge(i, root);
				x = root;
				ans++;
			}
		}else djs.merge(x, i);
		arr[i] = x;
	}
	if(root == -1){
		arr[1]=1;
		ans++;
	}
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++) cout<<arr[i]<<" \n"[i==n];
	return 0;
}