[数据结构与算法]【acwing】837. 连通块中点的数量

穿越隧道

在合并集合的代码基础上，统计每个集合中点的数量。（集合中所有点的数量放在祖先【根节点】维护)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N],si[N];
int n,m;
int find(int x){
    if(p[x] != x){
        p[x] = find(p[x]);
    }
    return p[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        p[i] = i;//每个点便是一个集合
        si[i] = 1;//每个集合中点的数量为1.
    }
    while(m--){
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0] == 'C'){
            scanf("%d%d",&a,&b);
            if(find(a) != find(b)){
                si[find(b)] += si[find(a)];//b的祖先的数量，加上a的祖先的数量
                p[find(a)] = find(b);//a的祖先的 父亲从无变为b的祖先
            }
        }
        else if(op[1]=='1'){
            scanf("%d%d",&a,&b);
            if(find(a) == find(b)){
                puts("Yes");
            }
            else{
                puts("No");
            }
        }
        else{
            scanf("%d",&a);
            printf("%d\n",si[find(a)]);
        }
    }
    return 0;
}