一、什么是并查集并查集Union-Find是一种用于处理不相交集合Disjoint Set的数据结构主要支持两种操作合并Union将两个元素所在的集合合并为一个集合查找Find查找某个元素所属的集合通常返回集合的代表元素并查集在解决连通性问题、图论算法、最小生成树Kruskal算法、网络连接检测等方面有着广泛的应用。二、并查集的核心思想并查集通过树形结构来表示集合每个集合用一棵树表示树的根节点作为该集合的代表。初始时每个元素都是独立的集合即每个元素都是自己的根节点。关键优化技术路径压缩Path Compression在查找过程中将查找路径上的所有节点直接连接到根节点按秩合并Union by Rank总是将较小的树连接到较大的树上避免树的高度增长过快三、Python并查集实现3.1 基础版本实现class UnionFind: def __init__(self, n): 初始化并查集每个元素都是独立的集合 self.parent list(range(n)) # 父节点数组 self.rank [0] * n # 秩树的高度 def find(self, x): 查找元素x的根节点带路径压缩 if self.parent[x] ! 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: return # 已经在同一个集合中 按秩合并 if self.rank[root_x] lt; self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] gt; self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 def connected(self, x, y): 判断两个元素是否连通 return self.find(x) self.find(y)/code/pre 3.2 简化版本适合竞赛 class DSU: def init(self, n): self.p list(range(n)) def find(self, x): if self.p[x] ! x: self.p[x] self.find(self.p[x]) return self.p[x] def union(self, x, y): self.p[self.find(x)] self.find(y)/code/pre 四、并查集应用示例 4.1 朋友圈问题 def find_circle_num(is_connected): LeetCode 547: 省份数量朋友圈问题 is_connected: n×n的邻接矩阵 n len(is_connected) uf UnionFind(n) for i in range(n): for j in range(i 1, n): if is_connected[i][j] 1: uf.union(i, j) 统计不同根节点的数量 roots set() for i in range(n): roots.add(uf.find(i)) return len(roots) 示例 is_connected [ [1, 1, 0], [1, 1, 0], [0, 0, 1] ] print(find_circle_num(is_connected)) # 输出: 2 4.2 岛屿数量II动态连通性问题 def num_islands2(m, n, positions): LeetCode 305: 岛屿数量II 每次添加一个陆地返回当前岛屿数量 uf UnionFind(m * n) grid [[0] * n for _ in range(m)] result [] count 0 directions [(0, 1), (0, -1), (1, 0), (-1, 0)] for x, y in positions: if grid[x][y] 1: result.append(count) continue grid[x][y] 1 count 1 idx x * n y # 二维坐标转一维索引 for dx, dy in directions: nx, ny x dx, y dy if 0 lt; nx lt; m and 0 lt; ny lt; n and grid[nx][ny] 1: nidx nx * n ny if not uf.connected(idx, nidx): uf.union(idx, nidx) count - 1 result.append(count) return result/code/pre 五、并查集的时间复杂度 使用路径压缩和按秩合并优化的并查集单次操作的平均时间复杂度接近常数级别 查找Find近似 O(α(n))其中α(n)是反阿克曼函数增长极其缓慢 合并Union近似 O(α(n)) 空间复杂度O(n)需要存储父节点和秩数组 对于大多数实际问题可以认为并查集操作是常数时间复杂度的。 六、常见问题与技巧 6.1 带权并查集 在某些问题中需要在并查集中维护额外的信息如距离、大小等 class WeightedUnionFind: def init(self, n): self.parent list(range(n)) self.weight [0] * n # 到父节点的权重 def find(self, x): if self.parent[x] ! x: root self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] self.parent[x] root return self.parent[x] def union(self, x, y, w): 合并x和y并满足weight[x] - weight[y] w root_x self.find(x) root_y self.find(y) if root_x root_y: return 调整权重 self.parent[root_x] root_y self.weight[root_x] w self.weight[y] - self.weight[x]lt;/codegt;lt;/pregt; 6.2 统计集合大小 class UnionFindWithSize: def init(self, n): self.parent list(range(n)) self.size [1] * n # 每个集合的大小 def find(self, x): ... 路径压缩 ... def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return 小集合合并到大集合 if self.size[root_x] lt; self.size[root_y]: root_x, root_y root_y, root_x self.parent[root_y] root_x self.size[root_x] self.size[root_y]lt;/codegt;lt;/pregt; 七、实战练习题目 LeetCode 547省份数量朋友圈问题 LeetCode 684冗余连接 LeetCode 685冗余连接II LeetCode 721账户合并 LeetCode 765情侣牵手 LeetCode 952按公因数计算最大组件大小 八、总结 并查集是一种高效处理连通性问题的数据结构掌握其核心思想和优化技巧对于解决许多算法问题至关重要。Python实现简洁明了通过路径压缩和按秩合并可以保证接近常数级别的时间复杂度。在实际应用中可以根据具体问题需求扩展并查集的功能如添加权重、统计大小等。 建议通过大量练习来熟练掌握并查集的应用场景和变形这对于提升算法解题能力大有裨益。