并查集的路径压缩是什么原理
  • 板块学术版
  • 楼主Fishmaster
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/12/6 18:52
  • 上次更新2023/11/3 22:47:03
查看原帖
并查集的路径压缩是什么原理
531258
Fishmaster楼主2021/12/6 18:52

rt。如下是并查集找祖先的代码(带路径压缩):

int find(int k){
	if(f[k]==k)return k;
	f[k]=find(f[k]); 
	return f[k];
}

而这个代码不是路径压缩:

int find(int k){
	if(f[k]==k)return k;
	return find(f[k]);
}

用这两个找祖先代码分别跑一遍 P3367,不知道为什么第一个能过,第二个 TLE。球球大家帮帮蒟蒻,这是什么原理,能讲讲吗 qwq

2021/12/6 18:52
加载中...