CodeEmperor @ 2024-08-13 10:28:21
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int n,m,p,fx[N];
int find(int i){
if(fx[i] == i ) return fx[i];
return fx[i]=find(fx[i]);//这里原本是return find(fx[i]) 结果会有3个样例超时但是后面改成 return fx[i]=find(fx[i])就样例全ac了
}
void insert(int x,int y)
{
int f1 = find(x),f2 = find(y);
if(f1 != f2){
fx[f1] = f2;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
fx[i] = i;
}
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x==1){
insert(y,z);
}else{
int f1 = find(y),f2 = find(z);
if(f1 == f2){
cout<<"Y"<<endl;
}else{
cout<<"N"<<endl;
}
}
}
return 0;
}
by Po7ed @ 2024-08-13 10:29:16
@CodeEmperor 路径压缩,并查集基本优化之一
by CodeEmperor @ 2024-08-13 10:34:08
@Po7ed 谢谢