关于路径压缩与按秩合并

我记得只有路径压缩并查集的复杂度是 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;
}

难道我学假了？？？