好的，各位观众老爷，今天咱们来聊聊一个听起来高大上，其实贼实用的算法——“并查集”（Disjoint-Set Union），也叫“不相交集合数据结构”。这玩意儿专门用来解决连通性问题，说白了，就是判断两个东西是不是一伙儿的，或者把两伙东西合并成一伙儿。
一、啥是连通性？这玩意儿有啥用？
连通性，简单来说，就是两个东西之间有没有路可以走通。比如，在一张地图上，两个城市之间有没有公路连接；在一个社交网络里，两个人之间有没有共同好友。
这玩意儿用处可大了，你想啊：
- 社交网络分析： 看看哪些人属于同一个社交圈子，挖掘潜在的群组关系。
- 网络路由： 确定网络中的节点是否连通，选择最佳的路由路径。
- 图像处理： 识别图像中的连通区域，进行图像分割。
- 迷宫生成与求解： 生成随机迷宫，或者找到迷宫的出口。
- 最小生成树（Kruskal 算法）： 在图中找到连接所有节点的最小代价的树。
二、并查集：你的连通性好帮手
并查集是一种数据结构，它维护着若干个不相交的集合。每个集合都有一个“代表元素”，可以理解为这个集合的“老大”。并查集主要提供两个操作：
- Find(x)： 找到元素 x 所在的集合的代表元素，也就是找到 x 的“老大”。
- Union(x, y)： 将元素 x 所在的集合和元素 y 所在的集合合并成一个集合，也就是让 x 和 y 的“老大”变成同一个。
三、并查集的实现：从青铜到王者
并查集的实现方式有很多种，咱们从最简单的开始，一步步进化。
1. 青铜：朴素实现
最简单的实现方式，就是用一个数组 parent 来记录每个元素的“爸爸”（也就是它的上级），根节点的“爸爸”指向自己。
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n)) # 初始化，每个元素都是自己的老大
def find(self, x):
"""找到元素 x 的老大"""
if self.parent[x] == x:
return x # x 自己就是老大
return self.find(self.parent[x]) # 递归向上找
def union(self, x, y):
"""合并 x 和 y 所在的集合"""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y # 让 x 的老大变成 y 的小弟这个实现很简单，但是效率很低。find 操作最坏情况下需要遍历整个树，时间复杂度是 O(n)。
2. 白银：路径压缩
路径压缩是一种优化 find 操作的方法。在 find 的过程中，我们将每个访问过的节点都直接指向根节点，这样下次再查找这个节点时，就可以直接找到根节点，而不需要再向上遍历。
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
"""找到元素 x 的老大，并进行路径压缩"""
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x]) # 路径压缩，让 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:
self.parent[root_x] = root_y路径压缩后的 find 操作，平均时间复杂度接近 O(α(n))，其中 α(n) 是反阿克曼函数，增长速度非常慢，可以认为是一个常数。
3. 黄金：按秩合并
按秩合并是一种优化 union 操作的方法。我们用一个数组 rank 来记录每个集合的“秩”，秩可以理解为集合的高度（实际上并不完全是高度，而是一个估计值）。在合并两个集合时，我们将秩较小的集合合并到秩较大的集合上，这样可以尽量保持树的平衡，避免出现退化成链表的情况。
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # 初始化，每个集合的秩都是 0
def find(self, x):
"""找到元素 x 的老大，并进行路径压缩"""
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""合并 x 和 y 所在的集合，并进行按秩合并"""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
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:
self.parent[root_y] = root_x # 秩相等时，随便合并一个
self.rank[root_x] += 1 # 被合并的集合的秩加 1按秩合并后的 union 操作，时间复杂度也是接近 O(α(n))。
4. 钻石：路径压缩 + 按秩合并
将路径压缩和按秩合并结合起来，可以得到性能最好的并查集实现。
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
"""找到元素 x 的老大，并进行路径压缩"""
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""合并 x 和 y 所在的集合，并进行按秩合并"""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
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:
self.parent[root_y] = root_x
self.rank[root_x] += 1这种实现的 find 和 union 操作的时间复杂度都接近 O(α(n))，可以认为是常数时间。
5. 王者：带权并查集
带权并查集是指在并查集的基础上，给每个节点增加一个“权值”，用来表示节点与其父节点之间的某种关系。例如，可以用来表示节点之间的距离、方向等等。
带权并查集在 find 和 union 操作中，需要维护节点的权值，使得权值能够反映节点之间的关系。
class WeightedDisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.weight = [0] * n # 初始权重为 0
def find(self, x):
"""查找根节点，并更新权重"""
if self.parent[x] == x:
return x
root = self.find(self.parent[x])
self.weight[x] += self.weight[self.parent[x]] # 更新权重
self.parent[x] = root
return root
def union(self, x, y, w):
"""合并集合，w 是 x 到 y 的权重"""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
self.weight[root_x] = self.weight[y] - self.weight[x] - w四、代码示例：解决实际问题
光说不练假把式，咱们来几个实际的例子。
例 1：判断图中的连通分量个数
给你一个无向图，判断图中共有多少个连通分量。
def count_connected_components(n, edges):
"""
计算无向图中的连通分量个数
n: 节点个数
edges: 边列表，例如 [[0, 1], [1, 2], [3, 4]]
"""
ds = DisjointSet(n)
for u, v in edges:
ds.union(u, v)
count = 0
for i in range(n):
if ds.parent[i] == i:
count += 1
return count
# 示例
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
components = count_connected_components(n, edges)
print(f"图中有 {components} 个连通分量") # 输出：图中有 2 个连通分量例 2：判断两个节点是否连通
给你一个无向图，判断两个节点是否连通。
def is_connected(n, edges, u, v):
"""
判断无向图中两个节点是否连通
n: 节点个数
edges: 边列表
u, v: 要判断的两个节点
"""
ds = DisjointSet(n)
for x, y in edges:
ds.union(x, y)
return ds.find(u) == ds.find(v)
# 示例
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
u = 0
v = 2
connected = is_connected(n, edges, u, v)
print(f"节点 {u} 和节点 {v} 是否连通：{connected}") # 输出：节点 0 和节点 2 是否连通：True
u = 0
v = 3
connected = is_connected(n, edges, u, v)
print(f"节点 {u} 和节点 {v} 是否连通：{connected}") # 输出：节点 0 和节点 3 是否连通：False例 3： 求解等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），返回 True，如果可以赋值变量，使得给定的等式方程为真；否则返回 False。
def equationsPossible(equations):
"""
判断等式方程是否可满足
equations: 等式方程列表，例如 ["a==b", "b!=c", "a==c"]
"""
ds = DisjointSet(26) # 26个字母
equalities = []
inequalities = []
for equation in equations:
if equation[1] == '=':
equalities.append((ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a')))
else:
inequalities.append((ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a')))
# 处理等式
for a, b in equalities:
ds.union(a, b)
# 处理不等式
for a, b in inequalities:
if ds.find(a) == ds.find(b):
return False # 如果相等，则方程不可满足
return True
# 示例
equations1 = ["a==b", "b!=c", "a==c"]
equations2 = ["a==b", "b==c", "a!=c"]
equations3 = ["a==b", "b==a"]
print(equationsPossible(equations1)) # False
print(equationsPossible(equations2)) # False
print(equationsPossible(equations3)) # True五、总结：并查集的武功秘籍
并查集是一种非常实用的数据结构，可以用来解决各种连通性问题。它的核心思想是：
- Find： 找到元素的“老大”，也就是它所在的集合的代表元素。
- Union： 合并两个集合，让它们的“老大”变成同一个。
通过路径压缩和按秩合并等优化技巧，可以将并查集的时间复杂度降低到接近常数级别。
六、并查集的适用场景
| 场景 | 并查集是否适用 | 备注 |
|---|---|---|
| 判断连通性 | 适用 | 快速判断两个元素是否属于同一个连通分量。 |
| 求解最小生成树 | 适用 | Kruskal 算法使用并查集来判断两个节点是否属于同一个集合，避免形成环路。 |
| 社交网络分析 | 适用 | 发现社交网络中的社群，分析用户之间的关系。 |
| 网络路由 | 适用 | 确定网络中的节点是否连通，选择最佳的路由路径。 |
| 动态连通性 | 适用 | 随着时间推移，元素之间的连通关系发生变化，并查集可以动态维护连通性信息。 |
| 元素数量不变 | 适用 | 并查集适合于元素数量固定的场景。如果元素数量动态变化，可能需要考虑其他数据结构。 |
七、一些需要注意的地方
- 初始化： 初始化时，每个元素都应该属于一个独立的集合，也就是让每个元素的“老大”指向自己。
- 路径压缩的副作用： 路径压缩会改变树的结构，但是不会影响并查集的正确性。
- 按秩合并的秩： 秩只是一个估计值，并不一定是树的实际高度。
好了，今天的并查集讲座就到这里。希望各位观众老爷能够掌握这门武功，在编程的道路上越走越远！下次再见！