CodeForces 755C PolandBall and Forest

题目链接：http://codeforces.com/contest/755/problem/C 题意：给你一个长度为n的序列，a[i]表示a[i]与i有条边相连，让你求这个序列构成的森林里有多少棵树 解析！：裸的并查集

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+100; int fa[maxn],a[maxn]; void init(int n) { for(int i=1;i<=n;i++) fa[i] = i; } int getfa(int x) { if(fa[x]==x) return fa[x]; return fa[x] = getfa(fa[x]); } void merge(int u,int v) { int t1 = getfa(u); int t2 = getfa(v); if(t1!=t2) fa[t1] = t2; } int main(void) { int n,x; scanf("%d",&n); init(n); for(int i=1;i<=n;i++) { scanf("%d",&x); int t1 = getfa(x); if(t1!=i) merge(x,i); } int ans = 0; for(int i=1;i<=n;i++) { if(fa[i]==i) ans++; } printf("%d\n",ans); return 0; }