827. Making A Large Island

这道题的关键点是如何快速根据区域内任意一点得到整个区域的面积，并查集是一种方案，查询每个点都能返回该点所在区域的唯一的根，另外一种方案就是用dfs或者bfs对该区域统一标号（着色）并对不同区域用不同的标号（颜色）来区分，查询每个点都能返回该区域的标号（颜色）
dfs O(n²) time O(n²) space

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        vector<int> areas(2); // areas表示不同颜色的岛屿面积，颜色从2开始
        int color = 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    areas.push_back(dfs(grid, i, j, color++)); // 用dfs对每个岛着色并统计面积记录下来
                }
            }
        }
        if (areas.size() == 3 && areas[2] == n * n) return areas[2]; // 如果整个grid就是一个岛，直接返回
        int res = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) { // 遍历每一个0，如果与某些岛相邻则累加其面积
                    unordered_set<int> s;
                    int sum = 1;
                    for (int k = 0; k < 4; ++k) {
                        int r = i + dr[k];
                        int c = j + dc[k];
                        if (isValid(r, c) && grid[r][c] > 1 && s.count(grid[r][c]) == 0) {
                            s.insert(grid[r][c]);
                            sum += areas[grid[r][c]];
                        }
                    }
                    res = max(res, sum);
                }
            }
        }
        return res;
    }

    int dfs(vector<vector<int>> &grid, int i, int j, int color) {
        grid[i][j] = color;
        int res = 1;
        for (int k = 0; k < 4; ++k) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (isValid(r, c) && grid[r][c] == 1) {
                res += dfs(grid, r, c, color);
            }
        }
        return res;
    }

    bool isValid(int i, int j) {
        return 0 <= i && i < n && 0 <= j && j < n;
    }

    int n, dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
};

union-find O(n²) time O(n²) space

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<int, vector<int>> borders;
        parent.resize(n * n);
        iota(begin(parent), end(parent), 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int k = i * n + j;
                if (grid[i][j] && area.count(k) == 0) {
                    area[k] = 1;
                }
                if (j > 0) {
                    if (grid[i][j]) {
                        if (grid[i][j - 1]) {
                            merge(k, k - 1);
                        } else {
                            borders[k- 1].push_back(k);
                        }
                    } else {
                        if (grid[i][j - 1]) {
                            borders[k].push_back(k - 1);
                        }
                    }
                }
                if (i > 0) {
                    if (grid[i][j]) {
                        if (grid[i - 1][j]) {
                            merge(k, k - n);
                        } else {
                            borders[k - n].push_back(k);
                        }
                    } else {
                        if (grid[i - 1][j]) {
                            borders[k].push_back(k - n);
                        }
                    }
                }
            }
        }
        if (area.empty()) return 1;
        if (borders.empty()) return n * n;
        int res = 0;
        for (auto&& p : borders) {
            unordered_set<int> s;
            int sum = 1;
            for (int i : p.second) {
                if (s.count(find(i))) continue;
                s.insert(find(i));
                sum += area[find(i)];
            }
            res = max(res, sum);
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            parent[px] = py;
            area[py] = area[py] + area[px];
        }
    }

    vector<int> parent;
    unordered_map<int, int> area;
};