5.5.2 并查集
原书定位
印刷页P186起,对应PDF第198页。下文为目视整理的知识提要;完整内容见原书对照。
并查集 DSU 用森林表示若干互不相交的集合。双亲数组 S[x] 非负时为父结点下标,根结点的负值可记录集合大小的相反数。
- 初始化:每个元素自成集合,
S[x]=-1。 Find(x)沿父指针寻找根;根相同表示属于同一集合。Union连接两个不同集合的根。传入普通元素时先查根;若已同根,不应再次连接。
未优化的树可能退化成链,查找最坏 ;已知两个根后仅作连接是 ,但整体合并操作还可能包含两次查找。

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

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

图5.30 并查集合并,原书P186。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图

