Codeforces Round #363 (Div. 2) D
题意：有N个点，每个点i都有一个父节点p[i]，如果“i == p[i]”则是说明i结点是根结点，现在我们给出这样的1～N的p[i]，这可能是不合法的，问，我们应该最少改变多少个使它变成一棵合法的树。
思路：有两种情况，一种是多棵树，另一种是一个环，也就是这个块是没有树，他们构成了一个环，如果是一个环的话，拆解环上任意一个结点都是可以的，去让它成为根结点，或者去连接上已经有的根结点，如果现在变成了个森林的图，我们要把多出来的根结点连接到其他的树的结点上面去。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 2e5 + 7; int N, head[maxN], cnt, p[maxN], root[maxN], num = 0, ans = 0, Stap[maxN], Stop = 0, rt; struct Eddge { int nex, to; Eddge(int a=-1, int b=0):nex(a), to(b) {} }edge[maxN]; inline void addEddge(int u, int v) { edge[cnt] = Eddge(head[u], v); head[u] = cnt++; } bool vis[maxN] = {false}, flag, used[maxN]; int id = 0, ST[maxN], ss; inline void dfs(int u) { vis[u] = true; ST[++ss] = u; used[u] = true; for(int i=head[u], v; ~i; i=edge[i].nex) { v = edge[i].to; if(!flag && used[v]) { flag = true; id = v; continue; } else if(used[v] || vis[v]) continue; dfs(v); } } inline void init() { cnt = 0; for(int i=1; i<=N; i++) head[i] = -1; } int main() { scanf("%d", &N); init(); for(int i=1; i<=N; i++) { scanf("%d", &p[i]); if(p[i] == i) { root[++num] = i; continue; } addEddge(p[i], i); } for(int i=1; i<=N; i++) Stap[++Stop] = i; rt = 0; while(num) { id = root[num]; rt = root[num]; dfs(root[num]); num--; if(num) { ans++; p[id] = root[num]; } } while(Stop) { while(Stop && vis[Stap[Stop]]) Stop--; if(!Stop) break; id = 0; flag = false; dfs(Stap[Stop]); while(ss) used[ST[ss--]] = false; if(!flag) continue; ans++; if(!rt) { p[id] = id; rt = id; } else p[id] = rt; } printf("%d\n", ans); for(int i=1; i<=N; i++) printf("%d ", p[i]); puts(""); return 0; }
