洛谷 P1892 [BOI2003]团伙（并查集）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int f[10005], ans;
 8 int n, m, p, q;
 9 char c;
10 
11 inline int find(int x){
12     if(f[x] != x)
13         f[x] = find(f[x]);
14     return f[x];
15 }
16 
17 int main(){
18     scanf("%d%d", &n, &m);
19     for(int i = 1; i <= n * 2; i++)//注意两倍 
20         f[i] = i;
21     for(int i = 1; i <= m; i++){
22         cin >> c >> p >> q;
23         if(c == ‘F‘){
24             f[find(p)] = find(q);//是朋友直接合并 
25         }
26         if(c == ‘E‘){
27             f[find(p + n)] = find(q);//反集合并两次，注意在find函数中的参数 
28             f[find(q + n)] = find(p);
29         }
30     }
31     for(int i = 1; i <= n; i++){
32         if(f[i] == i) ans++;//自己为根节点的个数，即集团个数 
33     }
34     printf("%d", ans);
35     return 0;
36 }