OI萌新玄关 关于非递归并查集的一点问题
  • 板块学术版
  • 楼主TMLY114514
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/9/9 08:52
  • 上次更新2024/9/9 17:32:37
查看原帖
OI萌新玄关 关于非递归并查集的一点问题
1121439
TMLY114514楼主2024/9/9 08:52

递归路径压缩:

int find(x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}

非递归:

int find(x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}

请问非递归的路径压缩为什么树高和递归相同,或者为什么复杂度没问题qwq

2024/9/9 08:52
加载中...