为什么全错哇，求助大佬

skiy_gyx @ 2019-07-23 22:54:24

#include<bits/stdc++.h>
using namespace std;
#define long long long
const int max_n=10000+10;
int n,m,far[max_n],rank[max_n];
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch=='-')f*=-1,ch=getchar();
    while(isdigit(ch))s=s*10+(ch-'0'),ch=getchar();
    return s*f;
}
int find(int x){
    if(far[x]==x)return x;
    else return find(far[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(rank[x]<rank[y]){
        far[x]=y;
    } else {
        far[y]=x;
        if(rank[x]==rank[y])rank[x]++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        far[i]=i;
        rank[i]=0;
    }
    while(m--){
        int z=read(),x=read(),y=read();
        if(z==1)merge(x,y);
        if(z==2){
            if(find(x)==find(y))cout<<"Y"<<"\n";
            else cout<<"N"<<"\n";
        }
    }
    return 0;
}

by ueettttuj @ 2019-07-24 07:54:30

@skiy_gyx

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

这里写错了

改为

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

by Refined_heart @ 2019-07-24 07:55:05

@skiy_gyx 今天我们学并查集，就看了一下，A了，给您发过去代码

#include<bits/stdc++.h>
using namespace std;
#define long long long
const int max_n=10000+10;
int n,m,far[max_n],rank[max_n];
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s*f;
}
int find(int x){
    return x==far[x]?x:far[x]=find(far[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y)far[x]=y;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        far[i]=i;
        rank[i]=0;
    }
    while(m--){
        int z=read(),x=read(),y=read();
        if(z==1)merge(x,y);
        if(z==2){
            if(find(x)==find(y))cout<<"Y"<<"\n";
            else cout<<"N"<<"\n";
        }
    }
    return 0;
}

by Refined_heart @ 2019-07-24 07:55:52

@skiy_gyx 这是改的您的代码，您的合并有些问题，要判断是否本来在同一个集合的，还有find函数要路径压缩的

by skiy_gyx @ 2019-07-24 07:57:46

@ueettttuj 万分感谢，可还是莫名WA

#include<bits/stdc++.h>
using namespace std;
#define long long long
const int max_n=10000+10;
int n,m,far[max_n],rank[max_n];
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch=='-')f*=-1,ch=getchar();
    while(isdigit(ch))s=s*10+(ch-'0'),ch=getchar();
    return s*f;
}
int find(int x){
    if(far[x]==x)return x;
    else return far[x]=find(far[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    far[x]=y;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        far[i]=i;
        rank[i]=0;
    }
    while(m--){
        int z=read(),x=read(),y=read();
        if(z==1)merge(x,y);
        if(z==2){
            if(find(x)==find(y))cout<<"Y"<<"\n";
            else cout<<"N"<<"\n";
        }
    }
    return 0;
}

by Refined_heart @ 2019-07-24 07:58:25

@skiy_gyx 您的合并函数……

by Smallbasic @ 2019-07-24 07:59:11

把:

cout << "N" << "\n";

改成

puts("N");

试试

by skiy_gyx @ 2019-07-24 08:00:10

@Refined_heart 主要是这样也错，我真的要自闭了。。

#include<bits/stdc++.h>
using namespace std;
#define long long long
const int max_n=10000+10;
int n,m,far[max_n],rank[max_n];
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch=='-')f*=-1,ch=getchar();
    while(isdigit(ch))s=s*10+(ch-'0'),ch=getchar();
    return s*f;
}
int find(int x){
    if(far[x]==x)return x;
    else return far[x]=find(far[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y)far[x]=y;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        far[i]=i;
        rank[i]=0;
    }
    while(m--){
        int z=read(),x=read(),y=read();
        if(z==1)merge(x,y);
        if(z==2){
            if(find(x)==find(y))cout<<"Y"<<"\n";
            else cout<<"N"<<"\n";
        }
    }
    return 0;
}

如上代码，依然全WA

by Refined_heart @ 2019-07-24 08:01:34

@skiy_gyx 上面那份代码是您的，您有两个错误，一个是find函数的路径压缩，另一个就是merge没有判断是否本身在一个集合内

by Refined_heart @ 2019-07-24 08:01:55

@skiy_gyx 我上面发的代码是A的啊

by ueettttuj @ 2019-07-24 08:02:02

@skiy_gyx 你快读打炸了吧~