想象一下，你是一个班级的班长，班里有很多同学。现在有一些同学互相认识（是朋友），但你需要快速知道：哪些同学是通过朋友关系连在一起的？比如，A认识B，B认识C，那么A、B、C应该是同一类人。同时，你还需要能快速判断两个同学是否认识（即使他们没直接说过话，但有共同认识的人也行）。这时候，有什么数据结构能帮你高效地解决这个问题呢？答案就是——并查集。
一、并查集是什么？¶
并查集（Union-Find）是一种用于管理元素分组的高效数据结构，核心功能是解决两个问题：
1. 合并（Union）：把两个不同的“组”（集合）合并成一个组；
2. 查询（Find）：判断两个元素是否属于同一个组。
它的名字里“并”对应“合并”，“查”对应“查询”，非常直观。
二、并查集的基本原理¶
并查集的底层用一个数组 parent 来表示每个元素的“父节点”。我们可以把每个组想象成一棵“树”，根节点（父节点指向自己的节点）是这个组的“代表”。
- 初始时，每个元素都是自己的组，所以 parent[i] = i（假设元素用数字编号）。
- Find 操作：查找元素的根节点（即它所在的组的代表）。
- Union 操作：将两个元素所在的组合并，让其中一个组的根节点指向另一个组的根节点。
举个例子：用并查集管理“朋友关系”¶
假设我们有 5 个人：小明（0）、小红（1）、小刚（2）、小李（3）、小芳（4）。初始时，每个人都是自己的组（parent = [0,1,2,3,4]）。
步骤 1：小明和小红是朋友
- 小明的根是 0，小红的根是 1。
- 合并两个组：让小红的父节点指向小明的根（parent[1] = 0）。现在小红和小明在同一个组，根是 0。
步骤 2：小刚和小红是朋友
- 小刚的根是 2，小红的根是 0（因为 parent[1]=0，小红的父节点是 0）。
- 合并两个组：让小刚的父节点指向 0（parent[2] = 0）。现在小刚、小明、小红在同一个组，根是 0。
步骤 3：小李和小明是朋友
- 小李的根是 3，小明的根是 0。
- 合并两个组：让小李的父节点指向 0（parent[3] = 0）。现在小李、小明、小红、小刚在同一个组，根是 0。
查询：判断小芳（4）是否和小明是朋友？
- 小芳的根是 4，小明的根是 0，根不同，所以不是朋友。
三、优化：让并查集更快¶
上面的例子是“朴素”的并查集，但如果合并和查询操作太多，朴素实现可能会变慢（比如树退化成链表）。路径压缩和按秩合并是关键优化：
1. 路径压缩：让“弯路”变“直路”¶
每次 Find 操作后，把路径上所有节点的父节点直接指向根节点。
比如，原来的路径是 A → B → C → 根，压缩后变成 A → 根、B → 根、C → 根，下次查询时直接一步到位。
比喻：就像你去学校需要绕很多弯路，老师让你下次直接抄近路，以后就不用再绕了。
2. 按秩合并：让“小树”依附“大树”¶
合并两个组时，把“树的高度较小”的组合并到“树的高度较大”的组的根节点下。
比喻：合并两个小组时，让矮个子小组（小树）的根指向高个子小组（大树）的根，避免大树被“压弯”。
四、并查集的核心代码（简化版）¶
以下是用 Python 实现的并查集（含路径压缩和按秩合并）：
class UnionFind:
def __init__(self, size):
self.parent = list(range(size)) # 父节点数组，初始每个元素自己是根
self.rank = [0] * size # 秩数组，记录树的高度
def find(self, x):
# 路径压缩：找到根节点，并把路径上的节点直接指向根
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 递归压缩父节点
return self.parent[x]
def union(self, x, y):
# 按秩合并：合并两个组
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y: # 已在同一组，无需合并
return
# 矮树合并到高树
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1 # 合并后高树高度+1
五、应用场景¶
并查集看似简单，却能解决很多实际问题：
- 网络连接：判断两台电脑是否在同一个局域网（通过路由器连接）。
- 家族关系：判断两个人是否有血缘关系（族谱合并）。
- 最小生成树：在 Kruskal 算法中，用并查集判断加入一条边后是否会形成环。
- 数学问题：比如判断两个数是否属于同一个等价类（如模运算下的等价关系）。
六、总结¶
并查集的核心是用数组维护“父节点”关系，通过 find 和 union 操作高效管理集合。路径压缩和按秩合并是关键优化，让它能在接近常数的时间复杂度下处理大量操作。它就像一个“高效的小组管理员”，无论合并还是查询，都能快速给出结果。
如果你遇到“分组”问题（比如判断是否在同一个集合），并查集会是一个简单又强大的工具！