0Pricing
Competitive Programming Academy · 课时

连通分量与洪水填充

统计岛屿并标记区域

连通分量与洪水填充 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

什么是连通分量

连通分量是一组彼此都可以到达的节点。一个图可以包含多个相互分离的组。🧩

统计连通分量

要统计连通分量，请从每个尚未访问的节点开始遍历。每个新的起点都会标记出一个完整的新组。

遍历所有节点

遍历从 1 到 n 的节点。当您找到一个仍然未访问的节点时，就发现了一个需要探索的新连通分量。

for s in range(1, n + 1):
    if not visited[s]:
        bfs_or_dfs(s)
        count += 1

每个连通分量遍历一次

这次内部 BFS 或 DFS 会将整个连通分量标记为已访问，因此外层循环下次就会跳过它。

网格也是图

二维网格是一个隐藏的图：每个单元格都是一个与邻居相连的节点。这就引出了经典的洪水填充思想。🗺️

四个方向

从一个单元格出发，通常可以向上、向下、向左和向右移动。将这些移动存储为方向向量，可以让代码保持整洁。

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

保持在网格内

移动前，请检查新行和新列是否在边界内。跳过这项检查会导致索引错误或答案错误。

if 0 <= nr < rows and 0 <= nc < cols:
    pass

填充一个区域

泛洪填充从一个单元格开始，扩展到所有相连的同类型单元格，就像油漆桶工具一样。

统计岛屿

要统计岛屿，请扫描网格；每遇到一个新的陆地单元格，就对它所属的整座岛屿进行泛洪填充，并将计数加一。

if grid[r][c] == '1' and not seen[r][c]:
    flood(r, c)
    islands += 1

标记区域

您可以在填充过程中为每个单元格存储一个标签。之后即可立即知道任意单元格属于哪个区域。

与网格大小成线性关系

每个单元格只访问一次，因此在网格上进行泛洪填充的复杂度为O(行数 × 列数)。这在竞赛限制内通常绰绰有余。

快速检查

如何统计连通分量？

回顾

从每个未访问节点出发进行遍历来统计连通分量，并在网格上使用泛洪填充来标记区域和统计岛屿。🎉

常见问题解答

「连通分量与洪水填充」课时是免费的吗？

是的 — 「连通分量与洪水填充」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「连通分量与洪水填充」这节课中我会学到什么？

统计岛屿并标记区域 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「连通分量与洪水填充」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 从输入构建邻接表
  2. 使用 BFS 求无权最短路径
  3. DFS、递归与迭代栈
  4. 连通分量与洪水填充
← 返回 Competitive Programming Academy