什么是并查集快速查找？
在算法的世界里，有一类问题看似简单，却常常让人陷入复杂逻辑的泥潭——那就是“判断两个元素是否属于同一集合”。比如，你要判断朋友圈里的两个人是不是同一个群聊里的成员，或者在地图上判断两个城市是否通过道路连通。
这类问题的本质，是处理动态的、不断合并的集合关系。如果每次都要遍历整个列表去检查，时间复杂度会迅速飙升，尤其是数据量大时，效率堪忧。这时候，并查集快速查找就派上了用场。
并查集（Union-Find）是一种专门用来处理这类“集合合并与查询”问题的数据结构。它的核心优势在于：支持高效的合并（Union）和快速查找（Find）操作。在理想情况下，单次操作的时间复杂度接近常数级别 O(1)，这得益于路径压缩和按秩合并等优化技巧。
想象一下，你有一堆散落的积木，每块积木代表一个元素。一开始，每个积木都是独立的。当你把两块积木拼在一起，它们就属于同一个“组合体”。并查集就是用来记录这种组合关系，并能立刻告诉你：这两块积木是不是在一个组合里。
这种结构在图论、网络连通性判断、最小生成树（Kruskal 算法）中极为常见。掌握它，就等于掌握了一把打开复杂连通性问题的钥匙。
并查集的基本原理
并查集的核心思想是：用树形结构表示集合。每个集合用一棵树来表示，树的根节点就是该集合的“代表元”（Representative）。所有属于同一集合的元素，最终都会指向同一个根节点。
举个例子：
假设我们有元素 A、B、C、D，初始时每个都是独立的集合。
- A → A
- B → B
- C → C
- D → D
此时，每个元素的父节点是自己，表示它自己就是根。
如果我们调用 union(A, B)，就把 A 和 B 合并成一个集合。通常做法是让 B 的父节点指向 A，或者反过来。假设我们让 B 指向 A，那么树结构变成：
- A → A
- B → A
- C → C
- D → D
此时，A 是集合的代表元。
当我们要判断 A 和 B 是否属于同一集合，就从 A 和 B 开始，沿着父节点不断向上找，直到找到根。如果两者的根相同，就说明在同一个集合。
这个查找过程，就是“并查集快速查找”的关键所在。
创建数组与初始化
在实现并查集时，我们通常使用一个数组 parent 来记录每个元素的父节点。
def initialize(n):
parent = list(range(n)) # 每个元素的父节点是自己
return parent
这段代码的意思是：创建一个长度为 n 的数组，索引 i 代表元素 i，parent[i] = i 表示元素 i 是自己的父节点，也就是根。
举个例子：n = 5，初始化后：
| 索引 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| parent | 0 | 1 | 2 | 3 | 4 |
此时每个元素都是独立集合。
💡 提示：这里使用
list(range(n))是 Python 的简洁写法，等价于[0, 1, 2, 3, 4]。数组索引从 0 开始，对应元素 0 到 n-1。
查找操作：路径压缩优化
查找操作 find(x) 的目标是：找到元素 x 所在集合的根节点。
def find(parent, x):
# 如果 x 的父节点不是自己，说明还没到根
if parent[x] != x:
# 递归查找根节点，并将路径上所有节点直接指向根
parent[x] = find(parent, parent[x])
return parent[x]
这个函数有两个关键点：
- 递归查找根：如果
parent[x] != x，说明 x 不是根，继续向上找。 - 路径压缩：在递归返回时，把
parent[x]直接设为根节点。这意味着，以后再查 x，就不用走完整条路径了。
举个例子：
假设我们有如下结构：
- 0 → 1 → 2 → 3（3 是根）
当执行 find(0) 时，递归过程如下：
- find(0) → find(1) → find(2) → find(3)
- find(3) 返回 3
- 回溯时：parent[2] = 3，parent[1] = 3，parent[0] = 3
最终，所有节点都直接指向根节点 3。
这就是“路径压缩”——把查找路径上的所有节点都拉直，直接连到根。这极大提升了后续查找效率，是“并查集快速查找”的核心优化之一。
合并操作：按秩合并提升性能
合并两个集合的操作叫 union(x, y)。它的逻辑是：把 y 所在集合的根，接到 x 所在集合的根下。
但为了保持树的平衡，避免出现“一条长链”的情况（比如 0→1→2→3→4，查找效率下降），我们引入“秩”（rank）的概念。
秩可以理解为树的高度的近似值。合并时，总是让秩小的树接到秩大的树下面。
def union(parent, rank, x, y):
# 先找到两个元素的根
root_x = find(parent, x)
root_y = find(parent, y)
# 如果根相同，说明已在同一集合，无需合并
if root_x == root_y:
return False # 合并失败，已连通
# 按秩合并：秩小的接到秩大的下面
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
# 秩相等，任选一个作为根，并增加其秩
parent[root_y] = root_x
rank[root_x] += 1
return True # 合并成功
这里的关键是：
find(parent, x)先找到根，避免直接合并非根节点。rank数组记录每个根节点的“层级高度”。- 合并后，如果两棵树秩相等，新根的秩加 1。
✅ 举个例子：两个秩为 2 的树合并，新树秩为 3。
按秩合并和路径压缩配合使用，能保证并查集操作的均摊时间复杂度趋近于 O(1)，这正是“并查集快速查找”能够高效运行的根本原因。
实际应用：判断网络连通性
让我们用一个真实场景来验证并查集的能力：判断一组节点是否全部连通。
问题描述：
有 5 个节点（0~4），给出若干连接关系（边），判断最终是否所有节点都连通。
n = 5
parent = list(range(n))
rank = [0] * n
def union(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if root_x == root_y:
return False
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
return True
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
for u, v in edges:
union(parent, rank, u, v)
root = find(parent, 0)
all_connected = all(find(parent, i) == root for i in range(1, n))
print("所有节点是否连通？", all_connected)
输出结果：True
✅ 这个例子展示了并查集在图连通性问题中的强大能力。通过多次
union和find，我们高效地判断了整个网络是否连通。
总结与建议
并查集快速查找，是解决动态连通性问题的利器。它的核心在于两个优化策略：路径压缩和按秩合并。前者让查找路径变短，后者让树保持平衡。
对于初学者来说，理解“根节点代表集合”这个概念是关键。每一次 find 操作，都是在“找家”；每一次 union，都是“搬家”或“合并家族”。
在实际开发中，这类结构常用于：
- 图的连通分量判断
- Kruskal 最小生成树算法
- 电路布线中的等价类判定
- 游戏中的好友系统（是否在同一个群组）
掌握并查集，不仅能提升算法能力，还能让你在面试中脱颖而出。
📌 最后提醒：不要把并查集当作“万能钥匙”。它适用于“只关心连通性，不关心路径”的场景。如果需要知道具体路径，还是得用 DFS 或 BFS。
并查集快速查找，不只是一个数据结构，更是一种思维方式。学会它，你就能在面对复杂关系问题时，快速找到简洁高效的解决方案。