130. Surrounded Regions - cocoder39/coco39_LC GitHub Wiki

class UnionFind {
public:
    UnionFind(int N) {
        for (int i = 0; i < N; i++) {
            parent.push_back(i);
            sz.push_back(1); 
        }
    }   
    bool isConnected(int i, int j) {
        return root(i) == root(j);
    }
    void unite(int i, int j) {
        int p = root(i);
        int q = root(j);
        if (p == q) return; //same tree
        
        if (sz[p] < sz[q]) { //smaller joins bigger for balance
            parent[p] = q;
            sz[q] += sz[p];
        } else {
            parent[q] = p;
            sz[p] += sz[q];
        }
    }
private:
    vector<int> parent;
    vector<int> sz;
    int root(int i) { //O(log*n) ~= O(1) in reality
        while (i != parent[i]) { 
            parent[i] = parent[parent[i]]; //flat the tree
            i = parent[i]; //move up
        }
        return i; //return root of a node
    }
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        if (n == 0) return;
        
        UnionFind uf(m * n + 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    int k = i * n + j;
                    if (i - 1 >= 0 && board[i - 1][j] == 'O')   uf.unite(k - n, k);
                    if (j - 1 >= 0 && board[i][j - 1] == 'O')   uf.unite(k - 1, k);
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1)   uf.unite(m * n, k);
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && ! uf.isConnected(m * n, i * n + j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
};