洛谷T3367 【模板】并查集 按秩合并

#include<cstdio>

using namespace std;

int max(int x,int y){
    if(x>y)return x;else return y;
}

int find(int);

int n,m,f,x,y,a,b;
int fa[10005],h[10005];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        h[i]=1;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&f,&x,&y);
        a=find(x);
        b=find(y);
        if(f==1){
            if(h[a]<h[b]){
                fa[a]=b;
                h[b]=max(h[b],h[a]+1);
            }
            else{
                fa[b]=a;
                h[a]=max(h[a],h[b]+1);
            }
        }
        else{
            if(a==b)printf("Y
");
            else printf("N
");
        }
    }
    
    return 0;
}

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