- 代码短, 面试易出, 思路精巧
- 支持操作: (在近乎
O(1)时间内) - 合并两个集合
- 询问两个元素是否在同一个集合当中
- 将每个集合分别存储在若干个树中, 根节点的编号就是集合的编号, 作为集合的代表节点; 对任意一个元素对其向上回溯到树根, 即可确定其属于哪一个集合
- 问题1: 如何判断树根? 答:
p[x] = x(p表示节点的父节点, 父节点为自身的只有根节点, 此为强制性定义) - 优化(路径压缩): 一旦找到根节点, 就将路径上所有点的父节点改为根节点(一旦搜索过则全部梳理好, 避免重复回溯), 优化之后复杂度接近
O(1) - 还有一种优化叫按秩合并, 但是效率不如路径压缩, 一般不采用
- 问题2: 如何求元素
x对应集合的编号? 答:while(p[x] != x) x = p[x]; - 问题3: 如何合并两个集合? 答: 将某一个集合对应的树整个插入到另一个树的祖宗节点下, 即令
p[root_x] = root_y即可 - 约定俗成的原则: 高的, 节点多的并查集作为parent(维护树的平衡)
- 注意: 可能需要维护额外的信息, 可以在对并查集操作时同步完成; 整个集合的额外性质信息应当以根节点为索引(对每个集合, 根节点唯一确定且各不相同)存在某一个数组中(如size); 单一节点的额外信息则以自身为索引记录
- 并查集的核心:
find()函数
