并查集【模板】

2018-01-12 19:36:23


并查集模板~

百思不得其解的时候过来看看

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m;
    int fa[200100];
    int find(int x)
    {
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            int k,a,b;
            scanf("%d%d%d",&k,&a,&b);
            if(k==2)
            {
                int x=find(a),y=find(b);
                if(x==y) printf("Y\n");
                else printf("N\n");
            }
            else
            {
                int x=find(a),y=find(b);
                if(x!=y) fa[x]=y;//注意,不是fa[a]=b!!!
            }
        }
        return 0;
}