2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

827. 最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

方法一：并查集

联通量问题还是并查集比较好思考。

基本思路分为以下2步

1. 对整个矩阵的所有的1进行联通，记录每个节点的森林大小。
2. 对每个0的四周进行单独讨论，加上下左右联通的森林大小即可。

其中难点在于第二步的处理。

首先准备一个带有统计并查集根节点森林大小的板子。对并查集里的任意点我们如果想知道他的联通量大小，我们可以这样。

dsu.sz(findRoot(x))

如何判断0节点四周的节点的森林大小呢？因为周围的四个点可能是已经连通了，不可能直接进行累加。

我们用一个哈希集合记录。对于四周的每个点，如果他的值是1，说明至少有大小为1的森林。我们把他的根节点插入哈希集合。

因为2个连通量的根节点是一样，我们就很巧妙的保证了只连通需要连通的森林。

坑点：可能没有0点。要特判。

class UF {
    // zerotrac2的并查集板子
public:
    vector<int> fa;
    vector<int> sz;
    int n; 
    int comp_cnt;

public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }

    int findset(int x) {
        return fa[x] == x ? x : fa[x] = findset(fa[x]);
    }

    void unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x != y) {
            if (sz[x] < sz[y]) {
                swap(x, y);
            }
            fa[y] = x;
            sz[x] += sz[y];
            --comp_cnt;

        }
    }

    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int res = 0;
        UF dsu(n * n);
        vector<pair<int, int>> zeros; // 对于每个0我们之后单独讨论即可。
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    if (i < n - 1 && grid[i + 1][j]) {
                        dsu.unite(i * n + j, (i + 1) * n + j);
                    } 
                    if (j < n - 1 && grid[i][j + 1]) {
                        dsu.unite(i * n + j, i * n + j + 1);
                    }
                } else zeros.emplace_back(i, j); // 统计所有的0.
            }
        }
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        // 对于每个0 统计每个相邻联通森林的大小即可。      
        for (auto& [x, y]: zeros) {
            unordered_set<int> connectedForest;
            for (int k = 0; k < 4; k++) {
                int ax = x + dx[k], ay = y + dy[k];
                if (ax >= 0 && ay >= 0 && ax < n && ay < n && grid[ax][ay]) {
                    connectedForest.insert(dsu.findset(ax * n + ay));
                }
            }
            int cur = 1;
            for (auto& x: connectedForest) {
                cur += dsu.sz[x];
            }
            res = max(res, cur);
        }
        if (zeros.empty()) return n * n;
        return res;
    }
};