并查集是一种处理不相交集合的合并与查询问题的数据结构，主要支持两种操作：
- Find：查询元素所属集合
- Union：合并两个集合
基本概念
数据结构表示
通常用树形结构表示集合，每个集合用一棵树表示，树的根节点作为该集合的代表元素。
核心操作
- 初始化：每个元素自成一个集合，父节点指向自己
- 查找(Find)：找到元素的根节点（代表元素）
- 合并(Union)：将两个集合合并为一个
实现方式
基础实现（无优化）
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root != y_root:
self.parent[y_root] = x_root优化技术
路径压缩（Path Compression）
- 在Find操作时将路径上的所有节点直接指向根节点
def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x]按秩合并（Union by Rank）
- 总是将较小的树合并到较大的树下
def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.rank[x_root] < self.rank[y_root]: self.parent[x_root] = y_root else: self.parent[y_root] = x_root if self.rank[x_root] == self.rank[y_root]: self.rank[x_root] += 1
时间复杂度分析
| 操作 | 无优化 | 仅路径压缩 | 仅按秩合并 | 两者结合 |
|---|---|---|---|---|
| Find | O(n) | O(α(n)) | O(log n) | O(α(n)) |
| Union | O(n) | O(α(n)) | O(log n) | O(α(n)) |
其中α(n)是反阿克曼函数，增长极其缓慢，可以认为是常数时间。
应用场景
- 连通性问题（如判断图中两点是否连通）
- 最小生成树算法（Kruskal算法）
- 动态连通性问题
- 图像处理中的区域合并
- 社交网络中的好友关系处理
示例代码（完整实现）
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
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):
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
if self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
else:
self.parent[y_root] = x_root
if self.rank[x_root] == self.rank[y_root]:
self.rank[x_root] += 1扩展功能
- 集合大小跟踪：记录每个集合的大小
- 集合计数：维护当前集合总数
- 撤销操作：支持回滚操作
并查集因其高效性和简洁性，在算法竞赛和实际工程中都有广泛应用。