Python并查集Union-Find — 路径压缩/按秩合并/连通分量/Kruskal并查集Disjoint Set Union, DSU是一种处理不相交集合的合并与查询问题的数据结构。常用于图论中的连通分量检测、环检测、最小生成树等场景。1. Union-Find 基础实现class UnionFind:并查集类初始时每个元素独立的集合def __init__(self, n):self.parent list(range(n)) # parent[i]表示i的父节点self.rank [1] * n # rank[i]表示以i为根的树的高度近似self.count 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 False # 已经在同一个集合中# 将高度较低的树接到高度较高的树下if self.rank[root_x] self.rank[root_y]:self.parent[root_x] root_yelif self.rank[root_x] self.rank[root_y]:self.parent[root_y] root_xelse:self.parent[root_y] root_xself.rank[root_x] 1 # 高度相同时合并后高度1self.count - 1 # 连通分量数减1return Truedef connected(self, x, y):判断x和y是否在同一个连通分量中return self.find(x) self.find(y)def get_count(self):返回当前连通分量的数量return self.count2. 路径压缩与按秩合并详解# 路径压缩Path Compression# 在find操作中将沿途所有节点直接指向根节点# 时间复杂度近乎O(1)阿克曼函数的反函数## 按秩合并Union by Rank# 将高度较小的树合并到高度较大的树中避免树过深## 同时使用两种优化后单次操作的平摊时间复杂度为O(α(n))# 其中α(n)是阿克曼函数的反函数在实际问题中α(n) 53. 检测图中的连通分量def count_components(n, edges):计算n个节点0~n-1在边列表edges中的连通分量数uf UnionFind(n)for u, v in edges:uf.union(u, v)return uf.get_count()# 示例0-1-2 3-4 五个节点两个连通分量n 5edges [(0, 1), (1, 2), (3, 4)]print(连通分量数:, count_components(n, edges)) # 24. 检测图中的环def has_cycle(n, edges):检测无向图是否有环如果两个节点已连通再添加边就形成环uf UnionFind(n)for u, v in edges:if uf.connected(u, v):return True # 发现环uf.union(u, v)return False# 示例0-1-2-0 三角形图有环edges_with_cycle [(0, 1), (1, 2), (2, 0)]print(有环吗:, has_cycle(3, edges_with_cycle)) # True5. 岛屿数量问题Number of Islandsdef num_islands(grid):计算二维网格中岛屿连通的1的数量if not grid or not grid[0]:return 0rows, cols len(grid), len(grid[0])uf UnionFind(rows * cols)# 将所有的0水域连接到一个虚拟节点但更简单的方法# 统计1的数量对相邻的1进行合并ones 0for r in range(rows):for c in range(cols):if grid[r][c] 1:ones 1idx r * cols c# 检查右边和下边的相邻陆地if r 1 rows and grid[r 1][c] 1:uf.union(idx, (r 1) * cols c)if c 1 cols and grid[r][c 1] 1:uf.union(idx, r * cols c 1)# 最终岛屿数量 所有1的数量 - 成功的合并次数# 更方便用一个单独的count跟踪return ones - (n * cols * rows - uf.get_count())# 简化版用DFS更直观def num_islands_dfs(grid):DFS解法标记已访问的陆地if not grid:return 0rows, cols len(grid), len(grid[0])def dfs(r, c):if r 0 or r rows or c 0 or c cols or grid[r][c] ! 1:returngrid[r][c] 0 # 标记为已访问dfs(r 1, c); dfs(r - 1, c)dfs(r, c 1); dfs(r, c - 1)count 0for r in range(rows):for c in range(cols):if grid[r][c] 1:count 1dfs(r, c)return countgrid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]print(岛屿数量:, num_islands_dfs(grid)) # 36. 朋友圈问题Friend Circlesdef find_circle_num(M):给定好友关系矩阵M计算朋友圈数量n len(M)uf UnionFind(n)for i in range(n):for j in range(i 1, n):if M[i][j] 1: # i和j是直接好友uf.union(i, j)return uf.get_count()M [[1, 1, 0],[1, 1, 0],[0, 0, 1]]print(朋友圈数量:, find_circle_num(M)) # 27. Kruskal 最小生成树算法def kruskal_mst(n, edges):Kruskal算法求最小生成树n: 节点数量edges: [(权重, u, v), ...]返回: (最小总权重, 选择的边列表)edges sorted(edges) # 按权重从小到大排序uf UnionFind(n)total_weight 0mst_edges []for weight, u, v in edges:if uf.union(u, v): # 如果u和v不在同一集合中total_weight weightmst_edges.append((u, v, weight))if len(mst_edges) n - 1: # MST有n-1条边breakreturn total_weight, mst_edges# 示例6个节点的加权图weighted_edges [(4, 0, 1), (2, 0, 2), (3, 1, 2),(1, 1, 3), (5, 2, 3), (6, 2, 4),(7, 3, 4), (8, 3, 5), (9, 4, 5)]total, mst kruskal_mst(6, weighted_edges)print(MST总权重:, total) # 21print(MST边:, mst)使用示例if __name__ __main__:uf UnionFind(10)uf.union(0, 1); uf.union(1, 2); uf.union(3, 4)uf.union(5, 6); uf.union(6, 7); uf.union(7, 8)print(0和2连通:, uf.connected(0, 2)) # Trueprint(0和3连通:, uf.connected(0, 3)) # Falseprint(连通分量数:, uf.get_count()) # 4
Python并查集UnionFind
Python并查集Union-Find — 路径压缩/按秩合并/连通分量/Kruskal并查集Disjoint Set Union, DSU是一种处理不相交集合的合并与查询问题的数据结构。常用于图论中的连通分量检测、环检测、最小生成树等场景。1. Union-Find 基础实现class UnionFind:并查集类初始时每个元素独立的集合def __init__(self, n):self.parent list(range(n)) # parent[i]表示i的父节点self.rank [1] * n # rank[i]表示以i为根的树的高度近似self.count 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 False # 已经在同一个集合中# 将高度较低的树接到高度较高的树下if self.rank[root_x] self.rank[root_y]:self.parent[root_x] root_yelif self.rank[root_x] self.rank[root_y]:self.parent[root_y] root_xelse:self.parent[root_y] root_xself.rank[root_x] 1 # 高度相同时合并后高度1self.count - 1 # 连通分量数减1return Truedef connected(self, x, y):判断x和y是否在同一个连通分量中return self.find(x) self.find(y)def get_count(self):返回当前连通分量的数量return self.count2. 路径压缩与按秩合并详解# 路径压缩Path Compression# 在find操作中将沿途所有节点直接指向根节点# 时间复杂度近乎O(1)阿克曼函数的反函数## 按秩合并Union by Rank# 将高度较小的树合并到高度较大的树中避免树过深## 同时使用两种优化后单次操作的平摊时间复杂度为O(α(n))# 其中α(n)是阿克曼函数的反函数在实际问题中α(n) 53. 检测图中的连通分量def count_components(n, edges):计算n个节点0~n-1在边列表edges中的连通分量数uf UnionFind(n)for u, v in edges:uf.union(u, v)return uf.get_count()# 示例0-1-2 3-4 五个节点两个连通分量n 5edges [(0, 1), (1, 2), (3, 4)]print(连通分量数:, count_components(n, edges)) # 24. 检测图中的环def has_cycle(n, edges):检测无向图是否有环如果两个节点已连通再添加边就形成环uf UnionFind(n)for u, v in edges:if uf.connected(u, v):return True # 发现环uf.union(u, v)return False# 示例0-1-2-0 三角形图有环edges_with_cycle [(0, 1), (1, 2), (2, 0)]print(有环吗:, has_cycle(3, edges_with_cycle)) # True5. 岛屿数量问题Number of Islandsdef num_islands(grid):计算二维网格中岛屿连通的1的数量if not grid or not grid[0]:return 0rows, cols len(grid), len(grid[0])uf UnionFind(rows * cols)# 将所有的0水域连接到一个虚拟节点但更简单的方法# 统计1的数量对相邻的1进行合并ones 0for r in range(rows):for c in range(cols):if grid[r][c] 1:ones 1idx r * cols c# 检查右边和下边的相邻陆地if r 1 rows and grid[r 1][c] 1:uf.union(idx, (r 1) * cols c)if c 1 cols and grid[r][c 1] 1:uf.union(idx, r * cols c 1)# 最终岛屿数量 所有1的数量 - 成功的合并次数# 更方便用一个单独的count跟踪return ones - (n * cols * rows - uf.get_count())# 简化版用DFS更直观def num_islands_dfs(grid):DFS解法标记已访问的陆地if not grid:return 0rows, cols len(grid), len(grid[0])def dfs(r, c):if r 0 or r rows or c 0 or c cols or grid[r][c] ! 1:returngrid[r][c] 0 # 标记为已访问dfs(r 1, c); dfs(r - 1, c)dfs(r, c 1); dfs(r, c - 1)count 0for r in range(rows):for c in range(cols):if grid[r][c] 1:count 1dfs(r, c)return countgrid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]print(岛屿数量:, num_islands_dfs(grid)) # 36. 朋友圈问题Friend Circlesdef find_circle_num(M):给定好友关系矩阵M计算朋友圈数量n len(M)uf UnionFind(n)for i in range(n):for j in range(i 1, n):if M[i][j] 1: # i和j是直接好友uf.union(i, j)return uf.get_count()M [[1, 1, 0],[1, 1, 0],[0, 0, 1]]print(朋友圈数量:, find_circle_num(M)) # 27. Kruskal 最小生成树算法def kruskal_mst(n, edges):Kruskal算法求最小生成树n: 节点数量edges: [(权重, u, v), ...]返回: (最小总权重, 选择的边列表)edges sorted(edges) # 按权重从小到大排序uf UnionFind(n)total_weight 0mst_edges []for weight, u, v in edges:if uf.union(u, v): # 如果u和v不在同一集合中total_weight weightmst_edges.append((u, v, weight))if len(mst_edges) n - 1: # MST有n-1条边breakreturn total_weight, mst_edges# 示例6个节点的加权图weighted_edges [(4, 0, 1), (2, 0, 2), (3, 1, 2),(1, 1, 3), (5, 2, 3), (6, 2, 4),(7, 3, 4), (8, 3, 5), (9, 4, 5)]total, mst kruskal_mst(6, weighted_edges)print(MST总权重:, total) # 21print(MST边:, mst)使用示例if __name__ __main__:uf UnionFind(10)uf.union(0, 1); uf.union(1, 2); uf.union(3, 4)uf.union(5, 6); uf.union(6, 7); uf.union(7, 8)print(0和2连通:, uf.connected(0, 2)) # Trueprint(0和3连通:, uf.connected(0, 3)) # Falseprint(连通分量数:, uf.get_count()) # 4
