【连通块 维护size】 连通块中的点数

传送门

题意

给定一个包含(n)个点（编号为(1sim n)）的无向图，初始时图中没有边。
现在要进行(m)个操作，操作共有三种：

• (（C，a，b）)，在点(a)和点(b)之间连一条边，(a)和(b)可能相等；
• (（Q_{1}，a，b）)，询问点(a)和点(b)是否在同一个连通块中，(a)和(b)可能相等；
• (（Q_{2}，a）)，询问点(a)所在连通块中点的数量；

数据范围

(1leq n,mleq 10^{5})

题解

• 维护集合数目的并查集，合并的时候将集合的数目合并即可
• 查询的时候不需要合并集合

Code

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int fa[N],sz[N];
int n,m;

int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void merge(int a,int b){
    int pa=find(a),pb=find(b);
    if(pa!=pb)  sz[pb]+=sz[pa],fa[pa]=pb;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;

    char op[3];
    int a,b;
    while(m--){
        cin>>op;
        if(op[0]=='C'){
            cin>>a>>b;
            if(a!=b) merge(a,b);
        }
        else if(op[1]=='1'){
            cin>>a>>b;  
            if(find(a) == find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else {
            cin>>a;
            cout<<sz[find(a)]<<endl;
        }
    }
}