5.5.2 并查集

教材导航 · 第5章

原书定位

印刷页P186起,对应PDF第198页。下文为目视整理的知识提要;完整内容见原书对照。

并查集 DSU 用森林表示若干互不相交的集合。双亲数组 S[x] 非负时为父结点下标,根结点的负值可记录集合大小的相反数。

  • 初始化:每个元素自成集合,S[x]=-1。
  • Find(x) 沿父指针寻找根;根相同表示属于同一集合。
  • Union 连接两个不同集合的根。传入普通元素时先查根;若已同根,不应再次连接。

未优化的树可能退化成链,查找最坏 O(n)O(n);已知两个根后仅作连接是 O(1)O(1),但整体合并操作还可能包含两次查找。

图5.28 并查集初始化

图5.28 并查集初始化,原书P186。

图5.29 并查集的树与双亲数组

图5.29 并查集的树与双亲数组,原书P186。

图5.30 并查集合并

图5.30 并查集合并,原书P186。

下级知识点

对应练习

5.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P186,PDF第198页

原书对照,原书P187,PDF第199页