并查集模版

经过两个优化后，并查集的效率变得非常高。对n个元素的并查集进行一次操作的均摊复杂度是O(a(n)) （a(n)是阿克曼函数的反函数），比优化前的O(log(n))还要快。

~所以来水一发题解~

代码如下：

#include <bits/stdc++.h>
#define il inline 
using namespace std;
int f[10004];
int h[10004];
int n,m;
il int read(){
	int f=1,x=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
il void init(){
	for(int i=1;i<=n;i++){
		f[i]=i;
		h[i]=0;
	}
}
il int Find(int i){
	if(f[i]==i){
		return f[i];
	}else{
		return f[i]=Find(f[i]);
	}
}
il void Merge(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa!=fb){
		if(h[fa]<h[fb]){
			f[fa]=fb;
		}else{
			f[fb]=fa;
			if(h[fb]==h[fa]){
				h[fa]++;
			}
		}
	}
}
int main(){
	
	n=read();m=read();
	init();
	while(m--){
		int z=read(),x=read(),y=read();
		if(z==1){
			Merge(x,y);
		}else{
			if(Find(x)==Find(y)){
				cout<<"Y"<<endl;
			}else{
				cout<<"N"<<endl;
			}
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;
int n,m;
int f[11451];
int find(int x){
    return x==f[x] ? x:(f[x]=find(f[x]));
}
int main(){
    cin>>n>>m;
    #define reg register
    for (reg int i=1;i<=n;i++){
        f[i]=i;
    }
    int opt,xx,yy;
    while(m--){
        cin>>opt>>xx>>yy;
        if(opt==1){
            f[find(xx)]=find(yy);
        } else{
            if(find(xx)==find(yy)) cout<<'Y'<<'\n';
            else cout<<'N'<<'\n';
        }
    }
    return 0;
}