题解 | 【模板】并查集

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

const int N=5e5+10;

int n,q;
int op;
int fa[N];
int nums_node[N];

void pre(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		nums_node[i]=1;
	}
	return;
}

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

void add(int x,int y){
	
	int fx=find(x);
	int fy=find(y);
	if(fx==fy) return;
	else{
		nums_node[fy]+=nums_node[fx];
		fa[fx]=fy;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>q;
	pre();
	
	int i,j;
	for(int k=1;k<=q;k++){
		cin>>op;
		if(op==1){
			cin>>i>>j;
			add(i,j);
		}else if(op==2){
			cin>>i>>j;
			if(find(i)==find(j)){
				cout<<"YES"<<endl;
			}else{
				cout<<"NO"<<endl;
			}
		}else if(op==3){
			cin>>i;
			cout<<nums_node[find(i)]<<endl;
		}
	}

    return 0;
}