并查集优化

用路径压缩与按大小/按秩合并,把并查集操作降到均摊接近常数。

标签 数据结构 / 并查集 / 路径压缩 / 按秩合并

朴素实现的问题

如果 find 只是沿父指针一路向上,unite 又总是把一棵树直接挂到另一棵树下,树可能退化成一条长链。

最坏情况下,单次 find 需要走 𝑂(𝑛) 步。优化要解决的就是“让树尽量矮”。

路径压缩

在 find(x) 返回根之后,把路径上经过的每个节点直接挂到根下面。

  • 下一次再查这些节点时,只需要一步就能到根。
  • 它不改变任何元素所属的集合,只改变树的形状。

按大小 / 按秩合并

合并两棵树时,把“较小”的树挂到“较大”的树下面:

  • 按大小:比较两个集合的元素个数。
  • 按秩:比较树的高度(或高度上界)。

这样树高不会轻易增长,避免长链。

两种优化一起用

路径压缩负责“查过的路径变短”,按大小/按秩负责“合并时不让树变高”。

两者结合后,单次操作的均摊代价接近常数;具体复杂度与证明见 并查集实现。

正确性

  • 路径压缩只改父指针,不改变根,因此不改变集合划分。
  • 按大小/按秩只决定谁挂在谁下面,根仍然是合并后集合的代表元。
  • 因此优化后的 find / unite 与朴素版本语义一致。

易错点

  • 路径压缩后,节点的父指针可能直接指向根;不要再用“父节点”推断集合关系。
  • 按大小合并时,size 只在根节点有意义;合并后要更新新根的大小。
  • 如果只做路径压缩、不做按大小合并,单次操作仍可能退化。
  • 带权并查集、可撤销并查集不能随意路径压缩,需要根据场景选择。

取舍与变式

  • 按大小 vs 按秩:两者效果相近;按大小更容易维护,按秩更贴近“树高”的直觉。
  • 递归 find 写法简洁,但深链可能爆栈;可以改成迭代。
  • 带权并查集:边带权值,维护到根的距离,用于关系推断。
  • 可撤销并查集:用按秩合并、不用路径压缩,支持回滚。
  • 扩展域并查集:把“敌人”拆成镜像节点,处理敌对/同类关系。
源码位置