LeetCode刷题实战：用并查集(Union-Find)秒杀“朋友圈”和“岛屿数量”这类题目（附Python/Java代码）

并查集实战用Union-Find高效解决LeetCode朋友圈与岛屿问题在算法面试中并查集Union-Find是一种常被忽视却威力巨大的数据结构。它能在近乎常数时间内完成集合合并与查询操作特别适合处理动态连通性问题。本文将以LeetCode经典题目547号「朋友圈」和200号「岛屿数量」为例手把手教你如何识别并查集适用场景并给出可直接套用的Python/Java代码模板。1. 并查集核心原理与优化策略并查集本质上是通过森林结构维护动态连通关系的工具。其核心操作包含Find查找元素所属集合即根节点Union合并两个元素所在的集合Connected判断两个元素是否连通1.1 三种实现方式对比实现方式Find时间复杂度Union时间复杂度空间复杂度适用场景Quick-FindO(1)O(N)O(N)查询频繁但合并少的场景Quick-UnionO(tree height)O(tree height)O(N)一般情况加权Quick-UnionO(logN)O(logN)O(N)大规模数据合并# 加权Quick-Union Python实现 class UnionFind: def __init__(self, size): self.root [i for i in range(size)] self.rank [1] * size def find(self, x): while x ! self.root[x]: x self.root[x] return x def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX ! rootY: if self.rank[rootX] self.rank[rootY]: self.root[rootY] rootX elif self.rank[rootX] self.rank[rootY]: self.root[rootX] rootY else: self.root[rootY] rootX self.rank[rootX] 1提示路径压缩优化可以在find操作中将节点直接链接到根节点进一步降低树高。只需在find方法中添加一行self.root[x] self.root[self.root[x]]2. LeetCode 547朋友圈问题实战题目描述一个班级中有N个学生给出M×M的矩阵表示朋友关系1表示直接朋友求朋友圈总数。2.1 问题转化技巧将每个学生视为节点朋友关系视为边。朋友圈数量等于连通分量的数量初始化并查集每个学生独立成集合遍历矩阵对每个为1的关系执行union操作最终统计根节点数量即为答案// Java解法 class Solution { public int findCircleNum(int[][] M) { int n M.length; UnionFind uf new UnionFind(n); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (M[i][j] 1) { uf.union(i, j); } } } return uf.count(); } class UnionFind { private int[] parent; private int count; public UnionFind(int n) { parent new int[n]; for (int i 0; i n; i) { parent[i] i; } count n; } public int find(int p) { while (p ! parent[p]) { parent[p] parent[parent[p]]; // 路径压缩 p parent[p]; } return p; } public void union(int p, int q) { int rootP find(p); int rootQ find(q); if (rootP rootQ) return; parent[rootP] rootQ; count--; } public int count() { return count; } } }2.2 复杂度分析时间复杂度O(N²α(N))其中α为反阿克曼函数通常认为接近O(1)空间复杂度O(N)用于存储父节点数组3. LeetCode 200岛屿数量问题题目描述给定由1陆地和0水组成的二维网格计算岛屿数量被水包围的陆地连通区域。3.1 并查集解法步骤初始化将每个1视为独立岛屿0不处理遍历网格对每个1检查其右侧和下侧相邻格子如果相邻也是1则执行union操作最终统计根节点数量即为岛屿数# Python解法 class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(rows * cols) directions [(1,0), (0,1)] # 只需检查右和下 count 0 for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 idx i * cols j for di, dj in directions: ni, nj i di, j dj if 0 ni rows and 0 nj cols and grid[ni][nj] 1: nidx ni * cols nj if not uf.connected(idx, nidx): uf.union(idx, nidx) count - 1 return count3.2 优化技巧虚拟节点法为所有水域创建公共父节点减少union操作按秩合并在union时总是将小树合并到大树下保持树平衡一维映射将二维坐标线性化为一维索引简化处理4. 并查集解题模板与调试技巧4.1 通用解题模板识别问题类型涉及动态连通性、分组或聚类的问题设计节点与边确定什么作为节点什么关系触发union初始化结构根据数据规模创建并查集实例处理边界条件如空输入、单个元素等特殊情况统计结果通过count或遍历计算连通分量4.2 常见错误排查数组越界确保find操作中的索引有效初始化错误父数组应初始化为各自索引重复合并union前应先检查是否已连通方向遗漏在网格问题中确保检查所有必要方向// 调试示例打印并查集状态 void debugPrint(UnionFind uf, int n) { System.out.print(Parent: ); for (int i 0; i n; i) { System.out.print(uf.find(i) ); } System.out.println(); }掌握并查集不仅能解决特定算法题更能培养将实际问题抽象为连通性问题的思维能力。建议在理解基础实现后尝试解决LeetCode 128最长连续序列、130被围绕的区域等扩展题目来巩固这一技术。