这道「岛屿题」用并查集做就体现出其威力了！

之前的岛屿题，用 DFS 和 BFS 来做要比用并查集更加好做并且高效，但是最对这一道题，827. 最大人工岛 来说，用并查集要更加好做。
【题目】给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿 由一组上、下、左、右四个方向相连的 1 形成。

题目要求是将一格 0 变成 1 之后再看最大的岛屿能够为多少，因此可以用上下左右分别判断岛屿的大小和当前的 0 组合记录最大的岛屿。思路如下：

• 第一遍遍历 grid：把所有的岛屿都记录下来，并且通过 rank 可以获得岛屿的面积；

• 第二遍遍历 grid：遇到为 0 的位置就记录将当前位置变为 1 之后，上下左右的岛屿面积连通起来的岛屿面积，具体做法：

  • 用一个变量 area = 1 记录面积；
  • 分别判断上下左右的位置是否为 1，如果为 1 的话获得该岛屿的面积，并累加到 area；
  • 还要记得多一个变量 seen 来记录岛屿是否已经见过。因为有可能上下左右有属于同一个岛屿的；

首先把并查集实现了：

class UnionFind {
public:
    int count;
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        count = n;
        parent = vector<int>(n);
        rank = vector<int>(n, 1);
        for (int i = 0; i < parent.size(); i++) {
            parent[i] = i;
        }
    }

    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    void Union(int x, int y) {
        int root_x = Find(x), root_y = Find(y);
        if (root_x == root_y) { return; }
        if (rank[root_x] >= rank[root_y]) {
            parent[root_y] = root_x;
            rank[root_x] += rank[root_y];
        } else {
            parent[root_x] = root_y;
            rank[root_y] += rank[root_x];
        }
    }
};

然后是题目主要逻辑：

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        // 遍历整个 grid 创建并查集
        int n = grid.size();
        UnionFind uf(n * n);
        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, -1, 1};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                            uf.Union(i * n + j, nx * n + ny);
                        }
                    }
                }
            }
        }

        int maxArea = 0;
        // 遍历所有的 0, 并且判断如果将这个 0 变为 1 之后的最大面积是多少
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 直接比较当前的面积大小
                    maxArea = max(maxArea, uf.rank[uf.Find(i * n + j)]);
                } else if (grid[i][j] == 0) {
                    int area = 1;  // 当前位置变为 1
                    set<int> seen;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                            int root_x = uf.Find(nx * n + ny);
                            if (seen.count(root_x) == 0) {
                                area += uf.rank[root_x];
                                seen.insert(root_x);
                            }
                        }
                    }
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};

LeetCode 上的题解为：并查集的威力终于发挥出来了！【C++ 并查集】