题解 | 【模板】并查集

#include <iostream>
#include <vector>
using namespace std;

class unionfind{
    private:
        vector<int>par,r,sz;//父节点数组，秩（深度）数组，集合数组
        int count;
    public:
    //初始化
    unionfind(int n){
        count=n;
        par.resize(n);
        r.resize(n,0);
        sz.resize(n,1);
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    //查找
    int find(int i){
    // 路径压缩：在查找过程中将路径上的所有节点直接连接到根节点
    if(par[i]!=i){
        par[i]=find(par[i]);
    }
    return par[i];//找根
    }
    //合并
    void unionset(int a,int b){
        int x=find(a);
        int y=find(b);
        if(x==y){return;}
        if(r[x]>r[y]){
            par[y]=x;
            sz[x]+=sz[y];
        }else if (r[x]<r[y]) {
            par[x]=y;
            sz[y]+=sz[x];
        }else {
            par[y]=x;
            r[x]++;
            sz[x]+=sz[y];
        }
        count--;
    }
    //查询连通性
    bool isconnected(int x,int y){
        return find(x)==find(y);
    }
    //查询集合大小
    int getsetsize(int x){
        return sz[find(x)];
    }
    //获取集合数量
    // 额外功能
    int getCount() {
        return count;
    }
};

int main() {
    int n,q;
    cin>>n>>q;
    unionfind uf(n);
    for(int i=0;i<q;i++){
        int op;
        cin>>op;
        if(op==1){
        int i,j;
        cin>>i>>j;
        uf.unionset(i,j);
        }else if (op==2) {
        int i,j;
        cin>>i>>j;
        cout<<((uf.isconnected(i,j))?"YES":"NO")<<endl;
        }else if (op==3) {
        int i;
        cin>>i;
        cout<<uf.getsetsize(i)<<endl;
        }
    }
    return 0;
}