C++ 连通块问题详解

在二维网格（Grid）或图像中，连通块 (Connected Component) 指的是一组相邻且具有相同属性（例如，值都为 1）的单元格。在经典的“岛屿问题”中，我们通常将：

• 值为 1 的格子视为 陆地 (Land)
• 值为 0 的格子视为 水域 (Water)

一个“岛屿”就是由若干个相互连接的陆地格子组成的连通块。

常见应用:

• 地图分析： 计算地图上的岛屿数量、湖泊数量。
• 图像处理： 识别图像中的物体、分割相同颜色或纹理的区域。
• 游戏开发： 区域划分、寻路（如判断两个区域是否连通）。
• 社交网络分析： 查找朋友圈或社群。

核心任务通常包括：计算连通块的数量、找出最大（或最小）的连通块面积、标记或修改特定的连通块等。

深度优先搜索 (Depth-First Search, DFS) 是解决连通块问题的经典递归方法。其核心思想是“一条路走到黑，走不通再回头”：

1. 遍历网格中的每一个单元格。
2. 如果遇到一个未访问过的陆地格子 (值为 1)，说明发现了一个新岛屿，岛屿计数加 1。
3. 从这个格子开始进行 DFS 探索：
   • 将当前格子标记为已访问（例如，修改值为 2 或使用一个额外的 visited 数组）。
   • 递归地访问其上、下、左、右四个方向的相邻格子。
   • 如果相邻格子是有效的陆地格子且未被访问，则继续对其进行 DFS 探索。
4. 一次完整的 DFS 会将整个岛屿的所有格子都标记为已访问，防止重复计数。

广度优先搜索 (Breadth-First Search, BFS) 是另一种常用的图遍历算法，特别适合查找最短路径。在岛屿问题中，它通过队列 (Queue) 来实现层序遍历：

1. 同样遍历网格，找到一个未访问的陆地格子 ('1')，岛屿计数加 1。
2. 将这个起始格子的坐标加入队列。
3. 将起始格子标记为已访问 ('2')。
4. 当队列不为空时，循环执行：
   • 从队列中取出一个格子（队首元素）。
   • 检查其上、下、左、右四个相邻格子。
   • 如果相邻格子是有效的、未访问的陆地格子，则将其标记为已访问，并加入队列。
5. 一次 BFS 过程会探索完与起始点相连的所有陆地格子，即一个完整的岛屿。

1. 最大岛屿面积 (Max Area of Island)

这是一个常见变种：计算所有岛屿中，面积最大的那个岛屿包含了多少个 '1'。我们可以在 DFS 或 BFS 探索一个岛屿的同时，计数其包含的格子数量。

// DFS 计算岛屿面积
// 返回从 (x, y) 出发能访问到的陆地格子总数
int dfsArea(vector>& grid, int x, int y) {
    int rows = grid.size();
    int cols = grid[0].size();

    // 边界检查 + 非陆地检查
    if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != '1') {
        return 0; // 不贡献面积
    }

    // 标记为已访问
    grid[x][y] = '2';

    // 当前格子面积为 1，加上来自四个方向的递归面积
    int currentArea = 1;
    currentArea += dfsArea(grid, x + 1, y);
    currentArea += dfsArea(grid, x - 1, y);
    currentArea += dfsArea(grid, x, y + 1);
    currentArea += dfsArea(grid, x, y - 1);

    return currentArea;
}

// 主函数计算最大岛屿面积
int maxAreaOfIsland(vector>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int rows = grid.size();
    int cols = grid[0].size();
    int maxArea = 0;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == '1') {
                int currentIslandArea = dfsArea(grid, i, j); // 计算当前岛屿面积
                maxArea = max(maxArea, currentIslandArea); // 更新最大面积
            }
        }
    }
    // 注意：同样需要恢复 grid 或使用 visited 数组
    return maxArea;
}

BFS 同样可以修改，在每次将格子加入队列时计数，或者在出队时计数。

2. 并查集 (Union-Find / Disjoint Set Union) 解法

并查集是一种高效处理“集合合并”和“查找元素所属集合”问题的数据结构。它也可以用来解决岛屿数量问题，尤其在动态场景（如岛屿可能合并）或需要频繁查询连通性时很有优势。

核心思想：

1. 将每个陆地格子 ('1') 初始化为一个独立的集合。水域格子 ('0') 不处理。
2. 遍历所有陆地格子。对于每个陆地格子，检查其右边和下边（避免重复检查）的相邻格子。
3. 如果相邻格子也是陆地，则使用并查集的 union 操作将这两个格子所在的集合合并。
4. 最终，并查集中不同的集合（根节点）的数量就是岛屿的数量。

#include <vector>
#include <numeric> // for std::iota

class UnionFind {
private:
    vector parent; // 存储每个节点的父节点
    vector rank;   // 优化：按秩合并 (可选，也可以按大小合并)
    int count;          // 连通分量的数量

public:
    // 构造函数：初始化 n 个独立的集合
    UnionFind(int n) : count(n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // 每个元素的父节点初始是自己
        rank.resize(n, 0); // 初始秩（树高）为 0
    }

    // 查找元素 x 所属集合的根节点 (带路径压缩优化)
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并元素 x 和 y 所在的集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) { // 如果它们不在同一个集合
            // 按秩合并：将秩小的树合并到秩大的树上
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX; // 秩相等，随便合并，但根节点秩要加 1
                rank[rootX]++;
            }
            count--; // 合并成功，连通分量数量减 1
        }
    }

    // 获取当前连通分量的数量
    int getCount() const {
        return count;
    }
};

// 使用并查集计算岛屿数量
int numIslands_uf(vector>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int rows = grid.size();
    int cols = grid[0].size();
    int waterCount = 0; // 统计水域数量

    // 初始化并查集，大小为 M*N，但只处理陆地
    UnionFind uf(rows * cols);

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == '1') {
                // 检查下方相邻格子
                if (i + 1 < rows && grid[i + 1][j] == '1') {
                    uf.unite(i * cols + j, (i + 1) * cols + j); // 合并
                }
                // 检查右方相邻格子
                if (j + 1 < cols && grid[i][j + 1] == '1') {
                    uf.unite(i * cols + j, i * cols + (j + 1)); // 合并
                }
            } else {
                waterCount++; // 统计水域格子
            }
        }
    }

    // 初始连通分量是所有格子 M*N
    // 减去水域格子，剩下的是初始陆地格子构成的独立集合数
    // 再减去合并掉的集合数 (M*N - uf.getCount())
    // 简化：最终连通分量数 uf.getCount() 包含了水域各自独立的集合
    // 所以岛屿数 = 总连通分量数 - 水域格子数
    return uf.getCount() - waterCount;
}

并查集在处理二维网格时，通常需要将二维坐标 `(r, c)` 映射到一维索引 `r * cols + c`。

恭喜你！通过本次学习，我们掌握了处理 C++ 中二维网格连通块（岛屿）问题的核心方法：

• 核心算法：
  • 深度优先搜索 (DFS): 使用递归或栈，深入探索路径。实现相对简洁，但需注意栈溢出风险。
  • 广度优先搜索 (BFS): 使用队列，层层扩展。无栈溢出风险，天然适合求最短路径。
• 关键技巧：
  • 边界判断： 访问相邻格子前，务必检查坐标是否在网格范围内 (0 <= x < rows && 0 <= y < cols)。
  • 标记已访问： 这是避免重复处理和死循环的核心。可以直接修改原网格（如 '1' -> '2'）或使用额外的 visited 数组/集合。
  • 遍历起点： 需要一个外层循环遍历网格所有单元格，确保每个潜在的岛屿起点都被考虑到。
• 扩展方法：
  • 计算面积： 在 DFS/BFS 过程中累加访问到的陆地格子数。
  • 并查集 (Union-Find): 另一种高效解法，特别适用于动态连通性或需要频繁查询的问题。需要将二维坐标映射到一维。
• 常见陷阱：
  • 忘记边界检查导致数组越界。
  • 忘记标记已访问导致无限循环或重复计数。
  • 并查集初始化或合并逻辑错误。

相关概念：

• 图论基础： 连通块问题本质上是图的连通性问题，网格可以看作一种特殊的图。
• 染色法： 将访问过的格子标记为不同状态（如 '2' 或 visited=true）可以看作一种简单的图染色。
• 其他网格问题： 如迷宫寻路、最短路径、包围区域（如 LeetCode 130. 被围绕的区域）等。

推荐 LeetCode 题目练习：

通过实战巩固理解：

• 200. 岛屿数量 (经典入门)
• 695. 岛屿的最大面积 (计算面积变种)
• 130. 被围绕的区域 (边界 DFS/BFS 应用)
• 323. 无向图中连通分量的数目 (并查集或 DFS/BFS 在一般图上的应用)
• 547. 省份数量 (邻接矩阵表示的图，类似岛屿)
• 547. 朋友圈 (同上题)

尝试用 DFS、BFS 和并查集（如果适用）分别解决这些问题，体会不同方法的优劣。