并查集

字数

233 字

阅读时间

1 分钟

---

一、作用

1. 合并两个集合
2. 查询某个元素的祖宗节点

二、优化

1. 路径压缩（最常用），时间复杂度为 $O(\log n)$ ，最坏为 $O(n)$
2. 按秩合并：合并集合时，每次将节点个数/树深度较少的合并到深度大的树中，时间复杂度为 $O(\log n)$，用得不多
3. 两者结合的优化，时间复杂度最优，为 $O(\alpha (n))$

• 凡是可以用并查集的题目，这两者的优化做法都可以看作是 $O(1)$ 的实践复杂度

三、扩展

1. 记录每个集合的大小
   • 将集合大小的属性绑定到根节点
2. 记录每个点到根节点的距离
   • 距离属性需要绑定到每个元素上

贡献者

freeway348

文件历史

最后编辑于 6 天前查看完整历史

39992-algorithm