Codeforces 755C：PolandBall and Forest（并查集）
标签：problems scanf tar 思路 inf merge color define 几分钟
Codeforces 755C：PolandBall and Forest（并查集）
#include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #include <cstdlib>
5 #include <algorithm>
6 #include <string>
7 #include <iostream>
8 #include <stack>
9 #include <map>
10 #include <queue>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 #define N 100010
15 #define INF 0x3f3f3f3f
16 int fa[N], num[N];
17
18 int Find(int x) {
19 if(x == fa[x]) return x;
20 return fa[x] = Find(fa[x]);
21 }
22
23 void Merge(int x, int y) {
24 x = Find(x), y = Find(y);
25 if(x == y) return ;
26 fa[x] = y;
27 }
28
29 int main()
30 {
31 int n;
32 scanf("%d", &n);
33 for(int i = 1; i <= n; i++) fa[i] = i;
34 for(int i = 1; i <= n; i++) scanf("%d", &num[i]);
35 for(int i = 1; i <= n; i++) {
36 Merge(i, num[i]);
37 }
38 int ans = 0;
39 for(int i = 1; i <= n; i++) if(fa[i] == i) ans++;
40 printf("%d\n", ans);
41 return 0;
42 }