关于P3367 的一点疑问
  • 板块学术版
  • 楼主tamamocross
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/9/2 11:55
  • 上次更新2023/11/2 23:56:18
查看原帖
关于P3367 的一点疑问
754444
tamamocross楼主2023/9/2 11:55

这个题里我写的按秩(集合大小)合并的并查集,没有写路径压缩,代码如下

#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个点。我想请问下是我上面的代码有问题呢,还是单纯按集合大小合并的时间复杂度不满足本题要求。

2023/9/2 11:55
加载中...