UnionFind Surrounded Regions

SurroundedRegions.cpp

class UnionFind {
    map<int, int> father;
    public:
    UnionFind(set<int> ids) {
        for(auto && id : ids) {
            father[id] = id;
        }
    }
    
    int find(int x) {
        int boss = father[x];
        while(boss != father[boss]) {
            boss = father[boss];
        }
        
        //compress chain
        int tmp = -1;
        int fa = x;
        while(fa != boss) {
            tmp = father[fa];
            father[fa] = boss;
            fa = tmp;
        }
        
        return boss;
    }
    
    void set_union(int x, int y) {
        int u_x = find(x);
        int u_y = find(y);
        
        if(u_x != u_y) {
            father[u_x] = u_y;
        }
    }
};

class Solution {
    bool isAtBoarder(int id, int n, int m) {
        int x = id / m;
        int y = id % m;
        return (x == 0 || x == n - 1) ||
        (y == 0 || y == m - 1);
    }
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void surroundedRegions(vector<vector<char>>& board) {
        if(board.size() == 0 || board[0].size() == 0) {
            return;
        }
        
        int n = board.size(), m = board[0].size();
        
        set<int> ids;
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[i].size(); j++) {
                if(board[i][j] == 'O') {
                    ids.insert(i * m + j);
                }
            }
        }
        
        UnionFind uf(ids);
        
        for(auto &&id : ids) {
            int x = id / m;
            int y = id % m;
            
            int dx[] = {0, 0, 1, -1};
            int dy[] = {1, -1, 0, 0};
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nid = nx * m + ny;
                
                if(nx >= 0 && nx < n && ny >=0 && ny < m &&
                    board[nx][ny] == 'O' && uf.find(id) != uf.find(nid)) {
                    uf.set_union(id, nid);
                }
            }
        }
        
        map<int, vector<int>> mymap;
        for(auto &&id: ids) {
            mymap[uf.find(id)].push_back(id);
        }
        
        for(auto it = mymap.begin(); it != mymap.end(); it++) {
            int cnt_boss = it->first;
            vector<int> &cnt_region = it->second;
            bool flip = true;
            for(auto &&id : cnt_region) {
                if(isAtBoarder(id, n, m)) {
                    flip = false;
                    break;
                }
            }
            if(flip) {
                for(auto &&id : cnt_region) {
                    int x = id / m;
                    int y = id % m;
                    board[x][y] = 'X';
                }
            }
        }
    }
};