Magallan_forever @ 2019-06-08 22:17:25

by Magallan_forever @ 2019-06-08 22:17:41

#include<cstdio>
#include<vector>
using namespace std;
template<int maxn>
struct union_set{
    int f[maxn];
    void init(){
        int i0;
        for(i0=0;i0<maxn;i0++){
            f[i0]=i0;
        }
    }
    int getf(int v){
        return v=getf(f[v]);
    }
    void merge(int a,int b){
        int fa=getf(a),fb=getf(b);
        f[fb]=f[fa];
    }
    bool in(int x,int y){
        return f[getf(x)]==f[getf(y)];
    }
};
union_set<10001> set_;
int main(){
    set_.init();
    int n,m,x,y,z;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&z,&x,&y);
        if(z^2){
            set_.merge(x,y);
        }
        else{
            puts(set_.in(x,y)?"Y":"N");
        }
    }
    return 0;
}

by Smile_Cindy @ 2019-06-08 22:19:31

@qbu666666

见getf函数。

#include<cstdio>
#include<vector>
using namespace std;
template<int maxn>
struct union_set{
    int f[maxn];
    void init(){
        int i0;
        for(i0=0;i0<maxn;i0++){
            f[i0]=i0;
        }
    }
    int getf(int v){
        if(v==f[v])return v;
        return f[v]=getf(f[v]);
    }
    void merge(int a,int b){
        int fa=getf(a),fb=getf(b);
        f[fb]=f[fa];
    }
    bool in(int x,int y){
        return f[getf(x)]==f[getf(y)];
    }
};
union_set<10001> set_;
int main(){
    set_.init();
    int n,m,x,y,z;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&z,&x,&y);
        if(z^2){
            set_.merge(x,y);
        }
        else{
            puts(set_.in(x,y)?"Y":"N");
        }
    }
    return 0;
}

by Magallan_forever @ 2019-06-08 22:23:31

@Alpha emmmmm……谢谢大佬