数据结构：并查集

数据结构：并查集

并查集（Disjoint Set Union，简称 DSU）是一种用于高效管理和合并不相交集合的数据结构，核心支持两种操作：

1. 查找（Find）：确定某个元素属于哪个集合（通常返回集合的代表元素）；
2. 合并（Union）：将两个不相交的集合合并为一个集合。

并查集的设计目标是在近乎常数时间内完成这两种操作，通过路径压缩和按秩合并两种优化策略，可将时间复杂度降低到近似O(1)O(1)O(1)（严格来说是阿克曼函数的反函数，增长极慢）。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、并查集的核心概念

1. 集合的表示

并查集采用树形结构表示集合，每个集合对应一棵树，树的根节点是该集合的代表元素。

• 每个元素存储一个指向父节点的引用，根节点的父节点是自身；
• 例如：集合{1,2,3}\{1,2,3\}{1,2,3}可表示为树1←2←3（根为 1），集合{4,5}\{4,5\}{4,5}可表示为树4←5（根为 4）。

2. 核心操作定义

3. 优化策略

未优化的并查集在最坏情况下会退化为链表（如连续合并1-2, 2-3, 3-4...），导致操作时间复杂度升至O(n)O(n)O(n)。两种优化策略可解决该问题：

（1）路径压缩（Path Compression）

在执行Find 操作时，将路径上所有节点的父节点直接指向根节点，扁平化树结构，减少后续查找的次数。

• 示例：查找元素 3 时，将路径1←2←3优化为1←2、1←3，下次查找 2 或 3 可直接找到根 1。

（2）按秩合并（Union by Rank/Size）

在执行Union 操作时，比较两棵树的“秩”（可以是树的高度或节点数量），将秩较小的树的根指向秩较大的树的根，避免树的高度过度增长。

• 按高度合并：维护每个根节点的高度，合并时矮树挂到高树的根下；
• 按大小合并：维护每个根节点的子节点数量，合并时小树挂到大树的根下。

二、并查集的实现步骤

1. 初始化：每个元素初始化为独立集合，父节点指向自身，秩初始化为 1（或高度初始化为 0）；
2. 查找操作（带路径压缩）：递归或迭代找到根节点，并将路径上所有节点的父节点指向根；
3. 合并操作（按秩合并）：找到两个元素的根节点，若根不同，则按秩合并两棵树，并更新秩的值；
4. 连通性查询：比较两个元素的根节点是否相同。

三、并查集的实现示例（Python）

classUnionFind:def__init__(self,size):"""初始化并查集，size 为元素总数（元素编号从 0 到 size-1）"""self.parent=list(range(size))# 父节点数组，parent[i] 表示 i 的父节点self.rank=[1]*size# 按大小合并：rank[i] 表示以 i 为根的集合的大小deffind(self,x):"""查找元素 x 的根节点，带路径压缩"""ifself.parent[x]!=x:# 路径压缩：将 x 的父节点直接指向根节点self.parent[x]=self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):"""合并元素 x 和 y 所在的集合，按秩合并"""root_x=self.find(x)root_y=self.find(y)ifroot_x==root_y:return# 已在同一集合，无需合并# 按大小合并：小树合并到大树下ifself.rank[root_x]<self.rank[root_y]:self.parent[root_x]=root_y self.rank[root_y]+=self.rank[root_x]else:self.parent[root_y]=root_x self.rank[root_x]+=self.rank[root_y]defis_connected(self,x,y):"""判断 x 和 y 是否连通"""returnself.find(x)==self.find(y)defget_set_size(self,x):"""获取元素 x 所在集合的大小"""root=self.find(x)returnself.rank[root]# 使用示例if__name__=="__main__":# 初始化 5 个元素的并查集（0-4）uf=UnionFind(5)# 合并集合uf.union(0,1)uf.union(1,2)uf.union(3,4)# 查询连通性print(uf.is_connected(0,2))# True（0、1、2 连通）print(uf.is_connected(0,3))# False（0 和 3 分属不同集合）# 合并两个集合uf.union(2,3)print(uf.is_connected(0,3))# True（所有元素连通）# 查询集合大小print(uf.get_set_size(0))# 5（所有元素在一个集合中）

四、并查集的时间复杂度

• 未优化：查找和合并操作的时间复杂度为O(h)O(h)O(h)，最坏情况h=nh=nh=n，时间复杂度O(n)O(n)O(n)；
• 带路径压缩 + 按秩合并：单次操作的均摊时间复杂度为O(α(n))O(\alpha(n))O(α(n))，其中α(n)\alpha(n)α(n)是阿克曼函数的反函数，增长极其缓慢。
  • 当n≤10600n \leq 10^{600}n≤10600时，α(n)≤5\alpha(n) \leq 5α(n)≤5，可近似认为是O(1)O(1)O(1)。

五、并查集的典型应用

并查集是解决连通性问题的利器，广泛应用于图论、算法竞赛和工程场景：

1. 图的连通分量统计

   • 场景：统计无向图中连通分量的数量；
   • 方案：遍历所有边，合并边的两个顶点，最终根节点的数量即为连通分量数。

2. 最小生成树算法（Kruskal 算法）

   • 场景：加权无向图的最小生成树求解；
   • 方案：将所有边按权重排序，依次选择边，若边的两个顶点不在同一集合，则合并（加入生成树），直到生成树包含n−1n-1n−1条边。

3. 检测图中的环

   • 场景：判断无向图是否存在环；
   • 方案：遍历所有边，若边的两个顶点已连通，则存在环；否则合并两个顶点。

4. 动态连通性问题

   • 场景：动态添加边并查询两点是否连通（如社交网络的好友关系、网络节点的连通性）；
   • 方案：用并查集维护动态连通关系，支持高效的合并和查询。

5. 岛屿数量问题（LeetCode 经典题）

   • 场景：给定二维网格，统计岛屿的数量（相邻的 1 视为一个岛屿）；
   • 方案：将每个 1 视为一个元素，合并相邻的 1，最终根节点的数量即为岛屿数。

6. 区间合并问题

   • 场景：合并多个重叠或相邻的区间；
   • 方案：将区间映射为元素，合并有交集的区间，最终得到不重叠的区间集合。

六、并查集的扩展

1. 带权并查集

   • 功能：不仅维护连通性，还维护节点到根节点的权值（如距离、差值）；
   • 应用：解决节点间关系的传递问题，如判断a到b的距离、a和b的大小关系等。

2. 可持久化并查集

   • 功能：支持查询历史版本的连通状态；
   • 应用：需要回溯的场景，如撤销之前的合并操作。

七、并查集与其他数据结构的对比

并查集是针对连通性问题的专用数据结构，在处理动态合并和查询的场景下，效率远超其他结构。