并查集优化
用路径压缩与按大小/按秩合并,把并查集操作降到均摊接近常数。标签 数据结构 / 并查集 / 路径压缩 / 按秩合并
朴素实现的问题
如果 find 只是沿父指针一路向上,unite 又总是把一棵树直接挂到另一棵树下,树可能退化成一条长链。
最坏情况下,单次 find 需要走 步。优化要解决的就是“让树尽量矮”。
路径压缩
在 find(x) 返回根之后,把路径上经过的每个节点直接挂到根下面。
- 下一次再查这些节点时,只需要一步就能到根。
- 它不改变任何元素所属的集合,只改变树的形状。
按大小 / 按秩合并
合并两棵树时,把“较小”的树挂到“较大”的树下面:
- 按大小:比较两个集合的元素个数。
- 按秩:比较树的高度(或高度上界)。
这样树高不会轻易增长,避免长链。
两种优化一起用
路径压缩负责“查过的路径变短”,按大小/按秩负责“合并时不让树变高”。
两者结合后,单次操作的均摊代价接近常数;具体复杂度与证明见 并查集实现。
正确性
- 路径压缩只改父指针,不改变根,因此不改变集合划分。
- 按大小/按秩只决定谁挂在谁下面,根仍然是合并后集合的代表元。
- 因此优化后的
find/unite与朴素版本语义一致。
易错点
- 路径压缩后,节点的父指针可能直接指向根;不要再用“父节点”推断集合关系。
- 按大小合并时,
size只在根节点有意义;合并后要更新新根的大小。 - 如果只做路径压缩、不做按大小合并,单次操作仍可能退化。
- 带权并查集、可撤销并查集不能随意路径压缩,需要根据场景选择。
取舍与变式
- 按大小 vs 按秩:两者效果相近;按大小更容易维护,按秩更贴近“树高”的直觉。
- 递归
find写法简洁,但深链可能爆栈;可以改成迭代。 - 带权并查集:边带权值,维护到根的距离,用于关系推断。
- 可撤销并查集:用按秩合并、不用路径压缩,支持回滚。
- 扩展域并查集:把“敌人”拆成镜像节点,处理敌对/同类关系。