题解 | 【模板】并查集

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=5e5+5;

struct UF {
    ll rank=0;
    UF* root;
    ll cnt=1;
};

UF a[N];

UF* Root(UF* a){
    if(a->root!=a){
        a->root=Root(a->root);
    }
    return a->root;
}

void merge(ll x, ll y) {
	UF* rx = Root(&a[x]);
	UF* ry = Root(&a[y]);
	if (rx == ry) return;

	if (rx->rank < ry->rank) {
		rx->root = ry;
        ry->cnt+=rx->cnt;
	}
	else {
		ry->root = rx;
        rx->cnt += ry->cnt;
		if (rx->rank == ry->rank) {
			rx->rank++;
		}
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,q;
    cin>>n>>q;
    for(ll i=1;i<=n;i++){
        a[i].root=&a[i];
    }
    while(q--){
        ll op;
        cin>>op;
        if(op==1){
            ll i,j;
            cin>>i>>j;
            merge(i,j);
        }else if(op==2){
            ll i,j;
            cin>>i>>j;
            if(Root(&a[i])==Root(&a[j])){
                cout<<"YES"<<'\n';
            }else{
                cout<<"NO"<<'\n';
            }
        }else if(op==3){
            ll i;
            cin>>i;
            cout<<Root(&a[i])->cnt<<'\n';
        }
    }

	return 0;
}