企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南以「算法通关手册」项目中的 0305. 岛屿数量 II 题解 为主体，讲解如何用并查集（Union Find）在二维网格上动态维护岛屿连通性并实时统计岛屿数量。读者学完后，将掌握"动态加边、实时计数"的并查集实战套路，包括二维坐标到一维索引的映射、四方向邻域合并、路径压缩与按秩合并的工程实现，并能独立解决同类"动态连通分量计数"问题。

一、题目概述

1.1 题目背景

本题属于「算法通关手册」题解库 0300-0399 分类下的困难题，标签为：并查集、数组、哈希表。

描述：给定一个大小为 $m \times n$ 的二维二进制网格 $grid$。网格表示一个地图，其中，$0$ 表示水，$1$ 表示陆地。最初，$grid$ 中的所有单元格都是水单元格（即，所有单元格都是 $0$）。

可以通过执行addLand操作，将某个位置的水转换成陆地。给你一个数组 $positions$，其中 $positions[i] = [ri, ci]$ 是要执行第 $i$ 次操作的位置 $(ri, ci)$。

要求：返回一个整数数组 $answer$，其中 $answer[i]$ 是将单元格 $(ri, ci)$ 转换为陆地后，地图中岛屿的数量。

说明：

• 岛屿：指的是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
• $1 \le m, n, positions.length \le 10^{4}$。
• $1 \le m \times n \le 10^{4}$。
• $positions[i].length == 2$。
• $0 \le ri \lt m$。
• $0 \le ci \lt n$。

进阶：你可以设计一个时间复杂度 $O(k \log(mn))$ 的算法解决此问题吗？（其中 $k == positions.length$）。

1.2 示例分析

示例 1：

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]] 输出：[1,1,2,3] 解释： 起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」） - 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。 - 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。 - 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。 - 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。

示例 2：

输入：m = 1, n = 1, positions = [[0,0]] 输出：[1]

从示例 1 可以看出一个关键细节：操作 #1 与操作 #2 添加的两块陆地上下相邻，因此合并为同一个岛屿，岛屿数量仍为 1；而操作 #3、#4 添加的陆地与已有岛屿不相邻，各自形成独立岛屿，所以数量依次递增。这正是本题"动态连通性"的本质。

二、解题思路：并查集（Union Find）

2.1 为什么选并查集

本题与静态的「岛屿数量」问题不同——网格最初全为水，陆地是逐个按位置添加的，每次添加后都要实时回答"当前有几个岛屿"。若每次都用 BFS/DFS 全图扫描，代价过高。

而"岛屿"的定义恰好是「被水包围、上下左右相邻的陆地连通块」，这天然对应不相交集合的合并与查询：

• 每次新增一块陆地，先让它自成一个集合（岛屿数量 +1）；
• 再检查它上下左右四个方向，如果相邻位置已经是陆地，就把两个集合合并（岛屿数量 -1）；
• 合并后集合的个数就是当前岛屿数量。

这正是「算法通关手册」在 并查集基础教程 中总结的核心能力：高效判断两个元素是否属于同一集合、高效合并两个集合，并在此基础上扩展出"统计集合个数"的能力。

2.2 算法设计四要素

1. 初始化：创建大小为 $m \times n$ 的并查集，初始时所有位置都是水（不属于任何岛屿）。
2. 添加陆地：对每个位置 $(r_i, c_i)$：
   • 将位置 $(r_i, c_i)$ 标记为陆地，并让它自成一个连通分量；
   • 检查四个方向 $(r_i-1, c_i)$、$(r_i+1, c_i)$、$(r_i, c_i-1)$、$(r_i, c_i+1)$ 是否已有陆地；
   • 如果相邻位置已是陆地，则与当前新添加的陆地合并到同一个连通分量中；
   • 统计当前连通分量的数量并记录。
3. 坐标转换：将二维坐标 $(r, c)$ 转换为一维索引 $index = r \times n + c$，便于并查集基于数组的操作。
4. 岛屿计数：每次添加陆地后，统计并查集中独立连通分量的数量。

其中第 3 点是实现层面的关键技巧：并查集基于一维数组实现，而网格是二维的，因此必须建立"二维坐标 ↔ 一维索引"的映射关系。只要保证r、c满足 $0 \le r \lt m$、$0 \le c \lt n$，r * n + c就能唯一对应一个网格单元格，且不会越界。

2.3 完整代码实现

以下代码完整继承自原题解文档，并补充了逐行注释：

class UnionFind: def __init__(self, n): """初始化并查集""" self.parent = [i for i in range(n)] # 父节点数组 self.rank = [0] * n # 秩数组，用于路径压缩优化 self.count = 0 # 连通分量数量 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): """合并两个节点""" 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_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: self.parent[root_y] = root_x self.rank[root_x] += 1 self.count -= 1 # 合并后连通分量数量减 1 return True def add_island(self, x): """添加一个新的岛屿""" if self.parent[x] != x: # 已经是陆地 return self.parent[x] = x self.count += 1 # 新增一个连通分量 class Solution: def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]: """使用并查集解决岛屿数量 II 问题""" # 方向数组：上、下、左、右 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 初始化并查集 uf = UnionFind(m * n) # 标记哪些位置是陆地 is_land = [False] * (m * n) result = [] for r, c in positions: # 将二维坐标转换为一维索引 index = r * n + c # 如果该位置已经是陆地，直接返回当前岛屿数量 if is_land[index]: result.append(uf.count) continue # 标记为陆地 is_land[index] = True uf.add_island(index) # 检查四个方向，合并相邻的陆地 for dr, dc in directions: new_r, new_c = r + dr, c + dc # 检查边界 if 0 <= new_r < m and 0 <= new_c < n: new_index = new_r * n + new_c # 如果相邻位置是陆地，进行合并 if is_land[new_index]: uf.union(index, new_index) # 记录当前岛屿数量 result.append(uf.count) return result

2.4 代码要点解读

• add_island与union配合维护count：每新增一块陆地先count += 1，每成功合并一次相邻陆地就count -= 1。这样uf.count始终精确等于当前岛屿数量，避免了每次操作后重新遍历全图统计的额外开销。这相当于在经典并查集基础上扩展了"集合计数"能力，与 并查集基础教程 第 5 节"根据具体需求对实现进行适当扩展"的建议完全一致。
• is_land布尔数组：并查集的parent数组本身无法区分"水"与"陆地"（初始时所有位置parent[i] = i，与未添加的陆地状态一致），因此需要独立的is_land数组记录哪些位置已变为陆地，只有"已标记为陆地"的相邻位置才参与合并。
• 重复位置的处理：positions中可能出现重复坐标，此时该位置已是陆地，直接返回当前count，避免重复add_island造成计数错误。
• 边界检查：四方向扩展时用0 <= new_r < m and 0 <= new_c < n保证不越界，这也是"地图四周被水包围"假设在代码层面的落实。

三、并查集底层原理与仓库源码印证

本题的解法建立在并查集数据结构之上。「算法通关手册」不仅在题解中给出实现，还在 并查集基础教程 中系统讲解了并查集的定义、两种实现思路（快速查询的数组实现、快速合并的森林实现）、路径压缩与按秩合并，仓库 并查集源码 给出了可复用的工程实现。

3.1 森林实现与路径压缩

题解代码中的find采用递归完全压缩：在查找根节点的过程中，把路径上经过的所有节点直接挂到根节点下，从而显著降低树的高度。仓库中的 tree_unionFind.py 则展示了工程上更推荐的隔代压缩迭代写法：

def find(self, x): while self.fa[x] != x: self.fa[x] = self.fa[self.fa[x]] # 隔代压缩优化 x = self.fa[x] return x

两种写法效果等价：都保证了后续查找接近 $O(1)$ 均摊代价。按 并查集基础教程 的建议，刷题时可优先采用代码更简洁的隔代压缩；本题题解采用"完全压缩 + 按秩合并"的组合，是一种更稳健的工程写法。

3.2 按秩合并

题解代码中的union采用按深度合并（Union By Rank）：合并时比较两个根节点的rank，将秩较小的树根挂到秩较大的树根下；深度相同时任选一方为新根并将rank + 1。这与仓库中的 tree_unionFind_UnoinByRank.py 实现思路一致。

按秩合并的意义在于：仅靠路径压缩无法控制整棵树的高度增长，而按秩合并能从合并策略上抑制树退化，二者结合可以保证并查集操作接近 $O(1)$ 的均摊复杂度。需要注意，路径压缩后rank不再代表真实树高，它只是合并时比较集合大小的辅助标记，正如教程第 3.3 节所强调的：不需要维护真实值，只要rank能反映两集合的相对大小即可。

四、复杂度分析

• 时间复杂度：$O(k \times \alpha(mn))$，其中 $k$ 是 $positions$ 的长度，$\alpha$ 是反阿克曼函数，可以认为是常数。每次操作需要检查四个方向并进行并查集操作。在同时使用路径压缩与按秩合并后，单次find/union的均摊代价接近 $O(1)$，因此总复杂度为 $O(k \times \alpha(mn))$，满足题目进阶要求 $O(k \log(mn))$ 的上界。
• 空间复杂度：$O(mn)$，用于存储并查集的父节点数组、秩数组和陆地标记数组。

五、与「岛屿数量 I」的对比

「算法通关手册」中收录了这道题的前作 0200. 岛屿数量（中等）。两者核心区别在于：

可以说，本题是把并查集"动态合并 + 实时计数"能力发挥到极致的经典题目，也是理解"离线 DFS"与"在线并查集"两种处理连通性问题思路差异的最佳样例。

六、举一反三：相关练习

本题属于「算法通关手册」并查集题目列表 中的重要成员。掌握本题的套路后，可以继续练习同系列题目巩固并查集的动态连通性应用：

• 0990. 等式方程的可满足性：先合并所有等式、再检验不等式的经典"先并后查"模型；
• 0547. 省份数量：统计无向图中连通分量数量；
• 0684. 冗余连接：在加边过程中检测成环；
• 1319. 连通网络的操作次数：连通分量计数与补边需求计算；
• 0323. 无向图中连通分量的数目：更纯粹的连通分量统计。

这些题目与本题共享"并查集维护连通分量数量"这一核心思想，反复练习后即可将并查集内化为解决图连通性问题的首选武器。

• 教程
• 文档
• 知识库