全MLE了.....

Lucien @ 2019-10-21 21:02:02

#include<iostream>
#include<cstdio>
using namespace std;
int fam[100010];
int elder(int x);
void unionfind(int x,int y);
int elder(int x){
    while(fam[x]!=x){
        fam[x]=elder(fam[x]);
        return fam[x];
    }
}
void unionfind(int x,int y){
    cout<<(elder(x)==elder(y)?'Y':'N')<<endl;
}
int main(){
    int n,m;
    int x,y,z;
    cin>>n>>m;
    for(int a=0;a<n;a++)
        fam[a]=a;
    for(int a=0;a<m;a++){

        cin>>z>>x>>y;
        if(z==1){
            fam[y]=x;
        }
        else{
            unionfind(x,y);
        }
    }

    return 0;
}

by AzusaCat @ 2019-10-21 21:08:56

从1开始编号

by bessie_goes_moo @ 2019-10-21 21:13:20

您合并的太草率了 find函数也没有边界

by Ghetto_Artist @ 2019-10-21 21:13:55

elder函数写错了，在合并的时候也要去查，就是要用代表合并，而且这样才会路径压缩，不至于查询一条长链。

#include<iostream>
#include<cstdio>
using namespace std;
int fam[100010];
int elder(int x);
void unionfind(int x,int y);
int elder(int x){return fam[x]==x ? x : fam[x]=elder(fam[x]);}
void unionfind(int x,int y){
    cout<<(elder(x)==elder(y)?'Y':'N')<<endl;
}
int main(){
    int n,m;
    int x,y,z;
    cin>>n>>m;
    for(int a=0;a<n;a++)
        fam[a]=a;
    for(int a=0;a<m;a++){

        cin>>z>>x>>y;
        if(z==1){
            fam[elder(y)]=elder(x);
        }
        else{
            unionfind(x,y);
        }
    }

    return 0;
}

by bessie_goes_moo @ 2019-10-21 21:15:19

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void cnt(int x,int y){
    if((x=find(x))^(y=find(y))) fa[x]=y;
}

by tuliwei @ 2019-10-21 21:57:02

事实上merge的时候并不需要判

by Lucien @ 2019-10-26 20:56:22

感谢各位!!懂了!!