题解 | 【模板】并查集

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

vector<int> father(500001,0);
vector<int> si(500001,1);
void init(){
    for(int i=0;i<father.size();i++){
        father[i]=i;
    }
}

int find(int u){
    return u==father[u]? u : father[u]=find(father[u]);
}

bool isSame(int u,int v){
    return find(u)==find(v);
}

void join(int u,int v){ 
    int rootu=find(u);
    int rootv=find(v);
    if(rootu==rootv) return;
    else if(si[rootu]>si[rootv]){
        father[rootv]=rootu;
        si[rootu]+=si[rootv];
        return;
    }
    else{
        father[rootu]=rootv;
        si[rootv]+=si[rootu];
        return;
    }
}

int size(int u){
    int x = find(u);
    return si[x];
}

int main() {
    init();
    int n,q;
    cin>>n>>q;
    for(int m=0;m<q;m++){
        int op,i,j;
        cin>>op;
        switch(op){
            case 1:
                cin>>i>>j;
                join(i,j);
                break;
            case 2:
                cin>>i>>j;
                if(isSame(i, j)) cout<<"YES"<<endl;
                else cout<<"NO"<<endl;
                break;
            case 3:
                cin>>i;
                int x = size(i);
                cout<<x<<endl;
        }
    }
    return 0;
}