求DALAO

P3367 【模板】并查集

jy20091121 @ 2023-09-13 20:28:44

#include<bits/stdc++.h>
using namespace std;
int fin[1233123];
int find(int k){
    if(fin[k]==k) return k;
    return fin[k]=find(fin[k]);
}
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fin[i]=i;
    for(int i=1;i<=m;i++){
    int x,y,z;
    cin>>z>>x>>y;
    if(z==1){
    fin[find(y)]=find(fin[x]);  
    }
    if(z==2){
    if(find(x)==find(y)){
    cout<<"Y"<<"\n";    
    }
    else{
    cout<<"N"<<"\n";    
    }
    }
    }   
    return 0;
}

为什么z==1时候 不能是fin[fin[y]]=find(fin[x])

而是fin[find(y)]=find(fin[x]) 求大佬指点没接触过并查集


by OldDriverTree @ 2023-09-13 20:31:36

因为你 fin[fin[y] ] 可能不是根节点,导致和原来父节点的边断开


by jy20091121 @ 2023-09-13 20:37:32

@OldDriverTree 谢谢DALAO orz orz %%


by jy20091121 @ 2023-09-13 20:38:27

@OldDriverTree 如果全部都是连好的是不是find(x)就等于fin[x]


by OldDriverTree @ 2023-09-13 20:42:16

@zhangjiayii 全部都是连好的是什么意思?


by jy20091121 @ 2023-09-13 20:46:18

@OldDriverTree 就是组成了一棵完整树的情况(fin[x]的值不是自己)


by OldDriverTree @ 2023-09-13 20:48:58

@zhangjiayii

  1. 根节点的 fin 为本身
  2. 还有可能没全路径压缩完

|