@[Judgelight](/user/461616) 这是一道橙题……
不要质疑一道通过76.27k的题目
by _Haoomff_ @ 2023-04-09 09:18:22
@[_Haoomff_](/user/368111) 但是我时间复杂度是错误的啊。
by Judgelight @ 2023-04-09 09:21:31
@[_Haoomff_](/user/368111) 不会回复可以不回复,人家说的是数据水不是数据错了。
by Sprague_Garundy @ 2023-04-09 09:22:08
$N \leq 10^4, O(n^2)$ 能过不是挺正常的。
by zym113 @ 2023-04-09 10:05:32
已AC,语言:C++14(GCC9)
```
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
int fa[Nmax];
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void merge(int a,int b){
int r1=find(a),r2=find(b);
if(r1!=r2) fa[r1]=r2;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--){
int z,x,y;
cin>>z>>x>>y;
if(z==1) merge(x,y);
else{
if(find(x)==find(y)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
```
by undefind @ 2023-06-17 09:36:55
@[zym113](/user/307500) 不对啊,复杂度不是 $O(nm)$ 的么
by y_kx_b @ 2023-07-27 21:40:45