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