11 min read2,110 words

并查集：连通性与集合合并

简介

并查集（Union-Find 或 Disjoint-Set Union, DSU）是一种用于处理动态连通性问题的高效树型数据结构。它主要支持两种操作：查找（Find）某个元素所属的集合（即找到其“代表元”），以及合并（Union）两个元素所在的集合。这种数据结构在解决网络连接、社交关系、图像分割、最小生成树算法（如 Kruskal）等场景中扮演着核心角色。其核心思想在于，通过维护一个父指针数组，将同一集合的元素组织成一棵树，树的根节点即为该集合的“代表元”。通过引入路径压缩和按秩合并这两种优化策略，可以将单次操作的均摊时间复杂度降至接近常数级别，使其成为解决大规模连通性问题的利器。

本章将深入剖析并查集的原理、模板实现、关键优化技术及其在算法竞赛和面试中的典型应用。我们将从基础概念出发，逐步构建完整的代码模板，并通过经典例题如“朋友圈”、“岛屿数量”和“等式方程的可满足性”来演示如何将并查集转化为解决实际问题的强大工具。理解并查集不仅有助于掌握一种数据结构，更能培养将复杂关系抽象为集合操作的计算思维。

核心概念

并查集的运作建立在几个核心概念之上。首先是代表元，它是每个集合的唯一标识符，通常选择集合中某个特定元素（在树形结构中即为根节点）来担任。判断两个元素是否属于同一集合，等价于判断它们的代表元是否相同。其次是父指针数组，通常用数组 parent 表示，其中 parent[i] 存储了元素 i 的父节点索引。如果 parent[i] == i，则说明元素 i 就是它所在集合的代表元（根节点）。

为了提高效率，必须采用两种优化策略。路径压缩 是在执行 find(x) 操作时，将查找路径上所有节点的父指针直接指向根节点，从而将树扁平化，极大加速后续查找。按秩合并 是在执行 union(x, y) 操作时，总是将深度较小（或“秩”较小，秩可以理解为树高的上界）的树合并到深度较大的树根下，以避免树退化成链表，保证树的平衡性。“秩”通常用另一个数组 rank 来维护。

下面的 Mermaid 图展示了并查集从初始状态，经过一系列合并操作，并最终进行路径压缩的典型过程，揭示了其内部集合组织结构的变化。

graph TD subgraph “初始状态：每个元素自成一集合” A0[“元素 0”] A1[“元素 1”] A2[“元素 2”] A3[“元素 3”] A4[“元素 4”] A0 --> A0 A1 --> A1 A2 --> A2 A3 --> A3 A4 --> A4 end subgraph “合并后：形成两棵树” B0[“元素 0 (根)”] B1[“元素 1”] B2[“元素 2”] B3[“元素 3 (根)”] B4[“元素 4”] B1 --> B0 B2 --> B1 B4 --> B3 end subgraph “路径压缩后：树被扁平化” C0[“元素 0 (根)”] C1[“元素 1”] C2[“元素 2”] C3[“元素 3 (根)”] C4[“元素 4”] C1 --> C0 C2 --> C0 C4 --> C3 end “初始状态：每个元素自成一集合” --> “执行 union(1,0), union(2,1), union(4,3)” --> “合并后：形成两棵树” “合并后：形成两棵树” --> “对元素2执行 find(2)” --> “路径压缩后：树被扁平化”

实战示例

下面提供一个功能完整、经过优化的并查集 Python 模板。它包含了路径压缩和按秩合并，并提供了解决动态连通性问题和判断图中是否有环的示例。代码中包含了详细的中文注释以解释每一步。

class UnionFind:
"""并查集 (Union-Find) 数据结构模板，包含路径压缩和按秩合并。"""
def __init__(self, n: int):
"""
初始化并查集。
:param n: 元素的总数，编号从 0 到 n-1。
"""
self.parent = list(range(n))  # 父指针数组，初始时每个元素的父节点是自己
self.rank = [0] * n           # 秩数组，初始为0
self.count = n                # 当前连通分量（集合）的个数
def find(self, x: int) -> int:
"""
查找元素 x 的根节点（代表元），同时进行路径压缩。
:param x: 目标元素
:return: 元素 x 所在集合的根节点
"""
# 如果 x 不是根节点，则递归地找到根节点，并直接将 x 的父指针指向根节点
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])  # 路径压缩核心步骤
return self.parent[x]
def union(self, x: int, y: int) -> bool:
"""
合并元素 x 和 y 所在的集合。使用按秩合并进行优化。
:param x: 第一个元素
:param y: 第二个元素
:return: 如果 x 和 y 原本不在同一集合，则合并成功返回 True；否则返回 False。
"""
root_x = self.find(x)
root_y = self.find(y)
# 如果根节点相同，说明已经在同一集合中，无需合并
if root_x == root_y:
return False
# 按秩合并：将秩较小的树合并到秩较大的树下
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
# 秩相等时，任意合并，并将新根的秩加1
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1  # 合并后，连通分量总数减1
return True
def is_connected(self, x: int, y: int) -> bool:
"""
判断元素 x 和 y 是否连通（属于同一集合）。
:param x: 第一个元素
:param y: 第二个元素
:return: 连通返回 True，否则返回 False。
"""
return self.find(x) == self.find(y)
# ========== 应用示例1: 动态连通性问题 ==========
def dynamic_connectivity_example():
"""演示并查集如何处理动态添加的连接关系。"""
print("=== 动态连通性示例 ===")
uf = UnionFind(5)  # 有5个节点：0,1,2,3,4
connections = [(0, 1), (1, 2), (3, 4)]
for a, b in connections:
uf.union(a, b)
print(f"连接 ({a}, {b}) 后，分量数: {uf.count}")
# 查询连通性
print(f"0 和 2 是否连通? {uf.is_connected(0, 2)}")  # True
print(f"0 和 3 是否连通? {uf.is_connected(0, 3)}")  # False
# ========== 应用示例2: 判断无向图中是否有环 ==========
def has_cycle_in_graph(edges: list, n: int) -> bool:
"""
使用并查集判断一个无向图中是否存在环。
:param edges: 图的边列表，每条边为 (u, v)
:param n: 图中节点的数量
:return: 存在环返回 True，否则返回 False。
"""
uf = UnionFind(n)
for u, v in edges:
# 如果两个顶点在连接前就已经在同一个集合中，说明这条边将形成一个环
if not uf.union(u, v):
return True
return False
if __name__ == "__main__":
dynamic_connectivity_example()
print("\n=== 判断图中是否有环 ===")
edges1 = [(0, 1), (1, 2), (2, 0)]  # 三角形，有环
edges2 = [(0, 1), (1, 2), (2, 3)]  # 链，无环
print(f"图1 (边: {edges1}) 是否有环? {has_cycle_in_graph(edges1, 4)}")
print(f"图2 (边: {edges2}) 是否有环? {has_cycle_in_graph(edges2, 4)}")

对比分析

并查集并非解决连通性问题的唯一方法。深度优先搜索（DFS）和广度优先搜索（BFS）也常用于判断图的连通性或寻找连通分量。下面的表格对比了并查集与DFS/BFS在解决此类问题时的特点。

方案	优势	劣势	适用场景
并查集 (Union-Find)	1. 动态操作高效：支持在线（online）的、交错的合并与查询操作，均摊时间复杂度接近O(α(n))，极快。 2. 空间复杂度低：通常只需两个大小为N的数组。 3. 代码简洁：核心操作仅需两个函数（find, union）。	1. 结构信息有限：主要回答“是否连通”，难以获取连通分量内的具体路径或全序结构。 2. 通常针对无向图：处理有向图的连通性（强连通分量）需要其他算法（如Kosaraju, Tarjan）。	1. 动态连通性问题（边逐步添加）。 2. Kruskal最小生成树算法。 3. 离线查询处理（如“等式方程的可满足性”）。 4. 需要频繁合并与查询的场景。
DFS / BFS 遍历	1. 信息丰富：一次遍历可获得连通分量内的所有节点、路径、层次等信息。 2. 通用性强：适用于有向图和无向图，可解决连通性、路径查找、环检测等多种问题。 3. 直观易懂：算法逻辑与图的结构直接对应。	1. 静态分析：图结构一旦确定，每次查询或添加边后可能需要重新遍历，不适合频繁动态修改的场景。 2. 时间复杂度：每次完整遍历的时间复杂度为O(V+E)，对于多次独立查询可能较慢。	1. 静态图分析：需要获取连通分量全部信息时。 2. 寻找路径。 3. 拓扑排序（有向无环图）。 4. 图的整体结构已知，且查询次数不多时。

最佳实践

始终使用优化：在实现并查集时，务必同时实现路径压缩和按秩合并。单独使用其中一种优化虽然有效，但两者结合才能达到最优的均摊时间复杂度。按秩合并在某些情况下可以用按大小合并（维护集合元素个数）替代，效果类似。
谨慎处理索引：并查集通常使用从0或1开始的连续整数作为元素ID。如果问题中的元素是字符串或其他类型，需要先建立到整型ID的映射（通常使用字典），再使用并查集进行操作。
理解“代表元”的语义：在复杂问题中，集合的“代表元”可以承载额外信息。例如，在“岛屿数量”问题中，代表元可以代表一片陆地；在“等式方程”问题中，代表元代表一组相等的变量。将问题元素正确归类到集合是解题关键。
利用分量计数：在初始化时记录分量数 count，每次成功执行 union 操作后将其减一。这个计数器在需要知道当前有多少个独立集合的问题中非常有用，例如“岛屿数量”和“省份数量”问题，最终答案就是 count 的值。
处理特殊关系：并查集本身处理等价关系（自反、对称、传递）。若问题包含不等、敌对等关系，可能需要使用扩展并查集，例如“带权并查集”或“种类并查集”，通过维护节点到根节点的距离（关系）来编码更多信息。

小结

并查集是一种以简洁代码实现高效集合合并与查询的经典数据结构。其核心在于通过父指针数组构建树形结构，并利用路径压缩与按秩合并两大优化达到近乎常数的操作效率。它特别擅长解决动态连通性问题、判断图中是否存在环，以及作为Kruskal算法的基础。通过本章的模板和例题分析，我们掌握了如何将现实世界的连通关系抽象为并查集操作，并理解了其与DFS/BFS等方法的适用场景差异。熟练运用并查集，是解决许多高级图论和关系型问题的关键一步。

下一节：前缀树与高级字符串算法