Leetcode 827: Making A Large Island

 https://leetcode.com/problems/making-a-large-island/description/

Notes:

This question can be viewed as a followup to find the largest island.

One idea is that: if we meet with a 0, then we need to check its four adjacent directions. 

For each of the four valid neighbors, if the value is 0, we can continue; 

else  we need to know: 1): the island id; 2): the size of island.

The reason for knowing 1) is that: the 1 on the left may be on the same island for 1 on other sides.

If they do not belong to the same island, then we can add them up.

The maximum value + 1 (flip one 0 to 1) is the final result.

For information 1) and 2), we can obtained by BFS, DFS, or UF. Here I just share codes with UF.

See the code below:

class Solution {
public:
    struct UF {
        vector<int> ps, cs;
        UF(int n): ps(n, 0), cs(n, 1) {
            iota(ps.begin(), ps.end(), 0);
        }
        int find(int x) {
            return ps[x] == x ? x : ps[x] = find(ps[x]);
        }
        void unite(int x, int y) {
            int a = find(x), b = find(y);
            if(a != b) {
                ps[b] = a;
                cs[a] += cs[b];
            }
        }
    };
    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid.front().size(), res = 0;
        UF uf(m*n);
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    int x = i-1, y = j-1;
                    if(x>=0 && grid[x][j] == 1) uf.unite(i*n+j, x*n+j);
                    if(y>=0 && grid[i][y] == 1) uf.unite(i*n+j, i*n+y);
                }
            }
        }
        vector<int> dirs = {-1, 0, 1, 0, -1};
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 0) {
                    set<int> st;
                    int count = 0;
                    for(int k=0; k+1<dirs.size(); ++k) {
                        int a = i + dirs[k], b = j + dirs[k+1];
                        if(a<0 || a>=m || b<0 || b>=n || grid[a][b] == 0) continue;
                        int r = uf.find(a*n + b);
                        if(!st.count(uf.ps[r])) {
                            count += uf.cs[r];
                            st.insert(r);
                        }
                    }
                    res = max(res, count+1);
                }
            }
        }
        return res == 0 ? m*n : res;
    }
};