好的，咱们今天来聊聊一个特别有意思的数据结构——并查集（Disjoint Set），也叫联合-查找数据结构（Union-Find Data Structure）。这玩意儿听起来好像很高大上，但实际上原理简单到令人发指，而且在解决某些特定类型的问题时，简直就是神器一般的存在。
一、什么是并查集？
想象一下，你是一个部落的首领，手底下管着一大堆小部落。这些小部落一开始各自为政，互不隶属。但是呢，随着时间的推移，有些小部落之间因为通婚、贸易、战争等各种原因，开始逐渐合并成更大的部落。你作为首领，需要随时知道哪些小部落属于同一个大部落，以及将两个小部落合并成一个大部落。
并查集就是用来解决这种问题的。它主要维护这样两个操作：
- 查找（Find）： 找到某个元素（小部落）所属的集合（大部落）的代表元素（首领）。
- 合并（Union）： 将两个元素（小部落）所在的集合（大部落）合并成一个集合。
二、并查集的实现方式
并查集的实现方式有很多种，最常见的也是最容易理解的一种就是使用树形结构来表示集合。每个集合用一棵树来表示，树的根节点就是这个集合的代表元素。
-
基本实现（朴素版）
我们用一个数组
parent来存储每个元素的父节点。一开始，每个元素都是一个独立的集合，所以每个元素的父节点都是它自己。class DisjointSet: def __init__(self, n): self.parent = list(range(n)) # 初始化，每个元素的父节点都是自己 def find(self, x): """查找元素x所属集合的代表元素""" if self.parent[x] == x: return x else: 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这个实现非常简单直观，但是效率比较低。因为在最坏的情况下，树可能会退化成一条链，导致
find操作的时间复杂度变成 O(n)。想象一下，如果所有小部落都一个接一个地合并，最后形成一个超级长的“蛇形”部落，那么每次查找都要从头跑到尾，那得多累啊！ -
路径压缩（Path Compression）
为了解决树退化成链的问题，我们可以使用路径压缩。路径压缩的思想是：在每次
find操作时，将查找路径上的所有节点的父节点都直接指向根节点。这样，下次再查找这些节点时，就可以直接找到根节点，大大提高了查找效率。class DisjointSet: def __init__(self, n): self.parent = list(range(n)) def find(self, x): """查找元素x所属集合的代表元素，并进行路径压缩""" if self.parent[x] == x: return x else: 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: self.parent[root_x] = root_y加了路径压缩之后，
find操作的时间复杂度大大降低，平均情况下接近 O(1)。想象一下，你每次去问一个部落的人他们的首领是谁，他们不仅会告诉你，还会顺便告诉他们的所有下属：“以后你们都直接找他，别来烦我了！” -
按秩合并（Union by Rank）
除了路径压缩，还可以使用按秩合并来优化并查集。秩（Rank）可以理解为树的高度，按秩合并的思想是：在合并两个集合时，将秩较小的树合并到秩较大的树上。这样可以尽量避免树的高度增加，从而减少
find操作的时间复杂度。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 else: 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按秩合并可以进一步优化并查集的性能，使其在最坏情况下的时间复杂度也接近 O(1)。想象一下，你合并两个部落的时候，总是让实力较弱的部落加入实力较强的部落，这样可以保证新的部落更加稳定，不容易发生内乱。
-
路径压缩 + 按秩合并（终极版）
将路径压缩和按秩合并结合起来使用，可以得到性能最佳的并查集实现。这种实现的时间复杂度几乎是常数级别的，非常高效。
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 else: 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
三、并查集的应用
并查集在解决连通性问题时非常有用。连通性问题是指判断两个元素是否属于同一个连通分量。比如：
- 判断图的连通性： 判断一个图中是否存在两个节点之间没有路径。
- 朋友圈问题： 判断一个社交网络中，有多少个朋友圈（互相认识的人组成一个朋友圈）。
- 迷宫问题： 判断一个迷宫中是否存在从起点到终点的路径。
- 最小生成树算法（Kruskal 算法）： 用于找到连接所有节点的最小代价的边集。
下面我们来看几个具体的例子：
-
判断图的连通性
给定一个图，判断该图是否连通。
def is_graph_connected(n, edges): """ 判断图是否连通 :param n: 节点数量 :param edges: 边列表，例如 [[0, 1], [1, 2], [2, 3]] :return: True if connected, False otherwise """ ds = DisjointSet(n) for u, v in edges: ds.union(u, v) # 检查所有节点是否属于同一个集合 root = ds.find(0) for i in range(1, n): if ds.find(i) != root: return False return True # 示例 n = 4 edges = [[0, 1], [1, 2], [2, 3]] print(f"图是否连通: {is_graph_connected(n, edges)}") # 输出: 图是否连通: True edges = [[0, 1], [2, 3]] print(f"图是否连通: {is_graph_connected(n, edges)}") # 输出: 图是否连通: False -
朋友圈问题
假设你是一个社交平台的管理员，你需要统计平台上有多少个朋友圈。如果两个人互相认识，或者通过朋友的朋友认识，那么他们就属于同一个朋友圈。
def count_friend_circles(n, relationships): """ 统计朋友圈的数量 :param n: 用户数量 :param relationships: 用户关系列表，例如 [[1, 1, 0], [1, 1, 0], [0, 0, 1]]，表示用户0和用户1认识，用户1和用户1认识，用户2和用户2认识 :return: 朋友圈的数量 """ ds = DisjointSet(n) for i in range(n): for j in range(i + 1, n): if relationships[i][j] == 1: ds.union(i, j) # 统计集合的数量 count = 0 for i in range(n): if ds.parent[i] == i: count += 1 return count # 示例 n = 3 relationships = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] print(f"朋友圈的数量: {count_friend_circles(n, relationships)}") # 输出: 朋友圈的数量: 2 -
Kruskal 算法
Kruskal 算法是一种用于求解最小生成树的贪心算法。它的基本思想是：将所有边按权重从小到大排序，然后依次将边加入到生成树中，如果加入该边会形成环，则跳过该边。并查集可以用来判断加入边是否会形成环。
def kruskal(n, edges): """ Kruskal 算法求解最小生成树 :param n: 节点数量 :param edges: 边列表，例如 [[0, 1, 10], [0, 2, 6], [1, 2, 5], [1, 3, 15], [2, 3, 4]]，表示节点0和节点1之间有一条权重为10的边 :return: 最小生成树的权重 """ edges.sort(key=lambda x: x[2]) # 按权重从小到大排序 ds = DisjointSet(n) mst_weight = 0 for u, v, weight in edges: if ds.find(u) != ds.find(v): ds.union(u, v) mst_weight += weight return mst_weight # 示例 n = 4 edges = [[0, 1, 10], [0, 2, 6], [1, 2, 5], [1, 3, 15], [2, 3, 4]] print(f"最小生成树的权重: {kruskal(n, edges)}") # 输出: 最小生成树的权重: 19
四、并查集的时间复杂度
| 操作 | 时间复杂度（朴素版） | 时间复杂度（路径压缩） | 时间复杂度（按秩合并） | 时间复杂度（路径压缩 + 按秩合并） |
|---|---|---|---|---|
find |
O(n) | 接近 O(1) | 接近 O(1) | 接近 O(1) |
union |
O(1) | O(1) | O(1) | O(1) |
| 初始化 | O(n) | O(n) | O(n) | O(n) |
五、总结
并查集是一种非常简单而强大的数据结构，它可以用来解决各种连通性问题。通过路径压缩和按秩合并等优化技巧，可以大大提高并查集的性能。
希望通过今天的讲解，大家对并查集有了更深入的理解。记住，在遇到连通性问题时，不妨试试并查集，说不定它能给你带来意想不到的惊喜！