救救我，并查集模板都不会打了QAQ

雨辰yoha @ 2019-10-01 11:46:48

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXX=200005;
int z[MAXX] ,x[MAXX],y[MAXX],fa[MAXX];
int getf(int need){
    if(fa[need]=need){
        return need;
    }
    fa[need]==getf(fa[need]);
    return fa[need];
}

bool find(int a,int b){
    int fa=getf(a);
    int fb=getf(b);
    if(fa==fb){
        return true;
    }
    return false;
}
void merge(int x,int y){
    if(!find(x,y)){
        fa[y]=fa[x];
    } 
    return ;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>z[i]>>x[i]>>y[i];
         if(z[i]==1){
            merge(x[i],y[i]);
         }else{
            if(find(x[i],y[i])){
                cout<<"Y"<<endl;
             }else{
                cout<<"N"<<endl;
             }
         }
    }

 } 

 4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

N
N
N
N

by 雨辰yoha @ 2019-10-01 12:59:32

还是不对QAQ

by 灵光一闪 @ 2019-10-01 12:59:36

@YUSS洛水天依 不应该是

void merge(int x,int y){
    fa[getf(y)]=getf(x);
    return;
}

吗？qwq

by Magallan_forever @ 2019-10-01 12:59:48

@YUSS洛水天依 f[getf(y)]=f[getf(x)]

by Alviss_lky @ 2019-10-01 13:00:32

%%%

by Walker_V @ 2019-10-01 13:00:52

@洛谷亿岁 我的错（打法不一样？）

by 雨辰yoha @ 2019-10-01 13:01:42

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXX=200005;
int z[MAXX] ,x[MAXX],y[MAXX],fa[MAXX];
int getf(int need){
    if(fa[need]=need){
        return need;
    }
    fa[need]=getf(fa[need]);
    return fa[need];
}
void Init() {
    for(int i=1;i<=n+10;i++) {
    fa[i]=i;
   }
}
bool find(int a,int b){
    int fa=getf(a);
    int fb=getf(b);
    if(fa==fb){
        return true;
    }
    return false;
}
//void merge(int x,int y){
//  if(!find(x,y)){
//      fa[getf(fa[y])]=fa[getf(fa[x])];
//  }    
//  return ;
//}
void merge(int x,int y) {
    int fx = getf(x);
    int fy = getf(y);
    if(fx != fy) {
        fa[fy] = fx;
    } 
   return;
}
int main()
{

    cin>>n>>m;
    Init();
    for(int i=1;i<=m;i++){
        cin>>z[i]>>x[i]>>y[i];
         if(z[i]==1){
            merge(x[i],y[i]);
         }else{
            if(find(x[i],y[i])){
                cout<<"Y"<<endl;
             }else{
                cout<<"N"<<endl;
             }
         }
    }

 } 

还是错了QAQ怎么办呀QAQ

by HaveFun @ 2019-10-01 13:02:16

@YUSS洛水天依 似乎结果一样qwq

by Walker_V @ 2019-10-01 13:03:05

找到了…… 第7行：

Right

if(fa[need]==need)

Wrong

if(fa[need]=need)

by HaveFun @ 2019-10-01 13:04:06

@YUSS洛水天依 stO

by Walker_V @ 2019-10-01 13:04:12

@QwQ永动鸭 这种情况下合并到另一个节点和另一个节点的父亲效果一样，但直接合并到两一个节点父亲更高效