支持的操作有
- MAKE-SET
- UNION
- FIND-SET
实现方式有
- 链表形式，在同一集合的元素使用链表串连起来，同时链表头表示集合的代表，其它元素有一个指针指向集合的代表
- 森林
对于森林表示方式的优化方式
- 路径压缩
- 按秩合并
在使用按秩合并时，集合中元素的秩的值不会超过
，集合操作总的时间复杂度为
，其中n表示元素个数，m表示总的操作数
对于支持删除节点的并查集，可以考虑使用虚拟节点，即在MAKE-SET时，使真实节点的父节点为虚拟节点。如下图，a表示真实节点，a’表示虚拟节点
应用
最小公共祖先
在有多个子结点时，在处理兄弟结点时，如果处理中间阶段，则会进入打印公共祖先逻辑
实践
UVa12232 Exclusive-OR
（加权并查集）
UVa11987 Almost Union-Find
(带有删除操作的并查集)
版权声明：本文为wuli2496原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。