# 第 7 节并查集知识总结

解决的是两个顶点是否连通的问题，可以用于检测图中是否存在环；
代表元法：采用 parent 数组实现，以每个结点的根结点作为代表元；
并查集的优化有两种策略：路径压缩：有「隔代压缩」与「完全压缩」。
- 「隔代压缩」性能比较高，虽然压缩不完全，不过多次执行「隔代压缩」也能达到「完全压缩」的效果，我本人比较偏向使用「隔代压缩」的写法。
- 「完全压缩」需要借助系统栈，使用递归的写法。或者先找到当前结点的根结点，然后把沿途上所有的结点都指向根结点，得遍历两次。
按「秩」合并，「秩」也有两种含义：
- 秩表示以当前结点为根结点的子树结点总数，即这里的「秩」表示 size 含义；
- 秩表示以当前结点为根结点的子树的高度，即这里的「秩」表示 rank 含义（更合理，因为查询时候的时间性能主要决定于树的高度）。
如果同时使用「路径压缩」与「按秩合并」，这里的「秩」就失去了它的定义，但即使秩表示的含义不准确，也能够作为合并时候很好的「参考」。在这种情况下，并查集的查询与合并的时间复杂度可以达到接近。

感兴趣的朋友可以在互联网上搜索关键字「并查集」「反阿克曼函数」深入了解同时使用「路径压缩」与「按秩合并」时候的并查集的时间复杂度。

我使用的策略是这样的（仅供参考）：用「隔代压缩」，代码比较好写。不写「按秩合并」，除非题目有一些关于「秩」的信息需要讨论。一般来说，这样写也能得到不错的性能，如果性能不太好的话，再考虑「按秩合并」。

# 并查集的时间复杂度分析

可以参考如下资料：

温馨提示：内容超纲，知道结论就好。

作者：liweiwei1419 链接：https://suanfa8.com/union-find/summarize 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。