Future_Present @ 2024-08-08 22:16:51
我用
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,m,pre[N],z,x,y;
int find(int x){
if(pre[x]==x) return x;
return pre[x]=find(pre[x]);
}
void Merge(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fx]=fy;
return;
}
bool check(int a,int b){
if(find(a)==find(b)) return true;
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
pre[i]=i;
while(m--){
cin>>z>>x>>y;
if(z==1)
Merge(x,y);
else if(z==2)
cout<<(check(x,y)?"Y":"N")<<endl;
}
return 0;
}
by mayike @ 2024-08-08 22:21:20
@2023csp
因为祖先可能还没更新到,必须 find
比如1的祖先是2,然后2的祖先是3,如果直接chk:pre[1]==pre[3]肯定错了
by Future_Present @ 2024-08-08 22:29:33
@mayike 感谢,已关
by cgxd @ 2024-08-08 22:51:44
不行,因为a和b的祖先没找到,暂且不能这样下定论,比如a的祖先是c,b的祖先是d,c和d有共同祖先,但是c和d不一样