我记得只有路径压缩并查集的复杂度是 $O(n\log n)$，路径压缩+按秩合并好像是 $O(n\alpha(n))$ 的，但为什么两种写法时间相差不多？

记录：只有路径压缩

路径压缩+按秩合并

代码：

路径压缩：

#include<bits/stdc++.h>
using namespace std;
int n,m,z,x,y;
int fa[10005];
struct bcj{
    int fa[10005];
    void init(){
    	for(int i=1;i<=n;++i)
    		fa[i]=i;
    }
    int find(int x){
    	if(x!=fa[x]) fa[x]=find(fa[x]);
    	return fa[x];
    }
    void Union(int x,int y){
    	int a=find(x);
    	int b=find(y);
    	if(a!=b)
    		fa[b]=a;
    }
}b;
int main()
{
	scanf("%d%d",&n,&m);
	b.init();
	while(m--)
	{
		scanf("%d%d%d",&z,&x,&y);
		if(z==1)
			b.Union(x,y);
		else
		{
			if(b.find(x)==b.find(y)) printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}

路径压缩+按秩合并：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int n,m;
struct bcj{
	int fa[maxn],g[maxn];
	void init(){
		for(int i=1;i<=n;++i)
			fa[i]=i,g[i]=1;
	}
	int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
	void merge(int x,int y){
		int u=find(x);
		int v=find(y);
		if(u==v) return;
		if(g[u]<g[v]) swap(u,v);
		fa[v]=fa[u];
		g[u]+=g[v];
	}
	bool check(int u,int v){return find(u)==find(v);}
}b;
signed main(){
	scanf("%d%d",&n,&m);
	b.init();
	while(m--){
		int op,u,v;
		scanf("%d%d%d",&op,&u,&v);
		if(op==1)
			b.merge(u,v);
		else
			putchar(b.check(u,v)?'Y':'N'),putchar('\n');
	}
	return 0;
}

难道我学假了？？？