并查集
并查集
zhou并查集
并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。
初始化
1 | int fa[MAXN]; |
查询
我们需要沿着树向上移动,直至找到根节点。
1 | int find(int x) |
路径压缩
为了避免形成链,优化查询的过程我们可以根据这个思路:把沿途的每个节点的父节点都设为根节点。去优化查询的过程,进行路径压缩。
1 | int find(int x) |
插入
1 | inline void merge(int i, int j) |
合并
要合并两棵树,我们只需要将一棵树的根节点连到另一棵树的根节点
1 | inline void merge(int i, int j) |
在合并的过程中有个问题,就是左边合并右边还是右边合并左边,到底谁作为根节点的问题。虽然无论怎么合并都能得到正确的结果,但不同的链接方式会影响到时间复杂度,具体来说,如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下,显然相比于另一种连接方案,接下来执行查找操作的用时更小(也会带来更优的最坏时间复杂度)。
此外,我们对于合并后的结构其实也可以做部分的路径压缩,也可以按秩合并,(秩就是子节点到根节点的深度,就是离了多少层)
但在实际操作中,即便不去纠结怎么合并,代码也往往能够在规定时间内完成任务。所以其实没那么重要。
删除
删除一个子节点可以把子节点的父节点设为自己,这样就完成了
结束
并查集有很多应用,比如最小生成树的Kruskal算法…
Comment
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果