这个题里我写的按秩(集合大小)合并的并查集,没有写路径压缩,代码如下
#include<iostream>
using namespace std;
const int Max=1e4+1;
int fa[Max],size[Max];
int get(int x){
if(fa[x]==x){
return x;
}
return get(fa[x]);
}
void Merge(int x,int y){
if(size[y]>size[x]){
swap(x,y);
}
size[x]+=size[y];
fa[get(y)]=get(x);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
size[i]=1;
}
while(m--){
int opt,x,y;
cin>>opt>>x>>y;
if(opt==1){
Merge(x,y);
}else{
cout<<(get(x)==get(y)?'Y':'N')<<'\n';
}
}
}
然后我在没吸氧的情况下就T了3个点。我想请问下是我上面的代码有问题呢,还是单纯按集合大小合并的时间复杂度不满足本题要求。