（并查集）连通块中点的数量

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 100010;
 5 int fa[N], cnt[N];
 6 int find(int x){
 7     if(x != fa[x]) fa[x] = find(fa[x]);
 8     return fa[x];
 9 }
10 int main(){
11     int n, m;
12     cin >> n >> m;
13     for(int i = 1; i <= n; i ++){
14         fa[i] = i;
15         cnt[i] = 1;
16     }
17     while(m --){
18         char op[5];
19         int a, b;
20         cin >> op;
21         if(op[0] == 'C'){
22             cin >> a >> b;
23             if(find(a) == find(b)) continue;
24             cnt[find(b)] += cnt[find(a)];//注意这两步不能写反，因为应该是先统计点的数量再连接两个集合
25             fa[find(a)] = find(b);
26         }else if(op[1] == '1'){
27             cin >> a >> b;
28             if(find(a) == find(b)) cout << "Yes" << endl;
29             else cout << "No" << endl;
30         }else if(op[1] == '2'){
31             cin >> a;
32             cout << cnt[find(a)] << endl;
33         }
34     }
35     return 0;
36 }