并查集

核心概念

并查集维护一个不相交集合的集合，并提供高效的操作来合并集合以及确定两个元素是否属于同一集合。它在涉及无向图连通性的问题中特别有用。

来源： thinkings/union-find.md17-19 thinkings/union-find.en.md17-19

核心API

并查集实现了三个主要操作

操作	描述	用例
`find(x)`	返回包含 x 的集合的代表元素	确定一个元素属于哪个集合
`union(p, q)`	合并包含元素 p 和 q 的集合	连接两个先前分离的组件
`connected(p, q)`	检查 p 和 q 是否属于同一集合	确定元素之间是否存在路径

来源： thinkings/union-find.md53-60 thinkings/union-find.en.md53-60

实现细节

基本结构

并查集将集合表示为树，其中每个元素指向其父节点。每个树的根作为该集合的代表。

在实现中，一个字典将每个元素映射到其父节点

{
 "0": "1",
 "1": "3",
 "2": "3",
 "4": "3",
 "3": "3"
}

来源： thinkings/union-find.md71-79 thinkings/union-find.en.md71-79

基本实现

该仓库提供了一个带优化功能的完整并查集模板

核心功能实现在以下方法中

find(x)：递归遍历父节点指针直到到达根节点
union(p, q)：通过将一棵树附加到另一棵树上来合并集合
connected(p, q)：检查两个元素是否共享同一个根

来源： thinkings/union-find.md166-198 thinkings/union-find.en.md164-196

优化

路径压缩

路径压缩在 find 操作期间使树结构扁平化，从而实现近乎常数时间的复杂度的操作

实现中在 find 方法中使用了路径压缩

来源： thinkings/union-find.md103-108 thinkings/union-find.en.md103-108

按大小/秩合并

该实现将较小的树附加到较大的树上以维持平衡

该实现使用 size 属性来跟踪树的大小并将较小的树附加到较大的树上

来源： thinkings/union-find.md187-194 thinkings/union-find.en.md187-194

加权并查集

对于具有加权边的图（如图距离），该仓库提供了一个加权并查集实现

此实现同时维护父节点指针和权重

来源： thinkings/union-find.md242-266 thinkings/union-find.en.md242-266

应用程序

环检测

并查集可高效检测无向图中的环

用于检测环的代码模板

来源： thinkings/union-find.md288-294 thinkings/union-find.en.md288-294

连通分量

并查集自然地跟踪图中的连通分量。实现维护一个计数器（cnt），该计数器在每次合并集合时减一

这对于询问连通区域或组件数量的问题很有用。

来源： thinkings/union-find.md195 thinkings/union-find.en.md193

最小生成树

并查集是 Kruskal 算法中寻找最小生成树的关键组成部分

来源： thinkings/union-find.md300 thinkings/union-find.en.md297

示例问题

该仓库包含几个使用并查集解决的问题

问题	描述	类型
547. 朋友圈	确定朋友圈的数量	连通分量
721. Accounts Merge	合并具有共同电子邮件的账户	连通分量
990. 等式方程	检查方程的可满足性	Union by Relation
1202. 最小字母序字符串	交换字符以最小化字符串	连通分量
1697. 边长受限的路径	检查具有受限边长度的路径	加权并查集

来源： thinkings/union-find.md308-314 thinkings/union-find.en.md305-311

实现示例：Accounts Merge

721. Accounts Merge 问题展示了并查集的实际应用

来自 problems/721.accounts-merge.md51-76 中的解决方案使用并查集来合并具有共同电子邮件的账户

复杂度分析

并查集操作的时间和空间复杂度取决于所使用的优化

实现	find	union	空间
基础	O(n)	O(n)	O(n)
路径压缩	O(log n)	O(log n)	O(n)
路径压缩 + 按秩合并	≈O(1)*	≈O(1)*	O(n)

*实际复杂度为 O(α(n))，其中 α 是反阿克曼函数，对于所有实际输入大小，其增长极慢且小于 5。

来源： thinkings/union-find.md274-278 thinkings/union-find.en.md274-278

总结

并查集是一种强大的数据结构，用于解决连通性问题。其效率源于两项关键优化

find 操作期间的路径压缩
通过按秩/大小合并来维护平衡树

当使用这些优化实现时，并查集操作近乎常数时间，使其成为处理大规模图连通性问题的绝佳选择。

来源： thinkings/union-find.md318-332 thinkings/union-find.en.md315-329

并查集