并查集

potatoplanet720 · 2024-11-23 19:16:43 · 算法·理论

/*
初始 每一个元素的祖宗是自己
合并x y
找到x的祖宗 y的祖宗
fa[x的祖宗]=y的祖宗
查找x y
找到x的祖宗 y的祖宗
x的祖宗=y的祖宗
*/
#include<bits/stdc++.h>
using namespace std;
int fa[200005];
int find(int x){
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
} 
void go(int x,int y){
    fa[fa[x]]=fa[y];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int p,y,x;
        scanf("%d%d%d",&p,&x,&y);
        find(x),find(y);
        if(p==1){
            go(x,y);
        }else{
            if(fa[x]==fa[y]) cout<<"Y";
            else cout<<"N";
            cout<<endl;
        }
    }
    return 0;
}