C++ Union Find


  • 0
    G
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            int m = grid.size(), n = m ? grid[0].size() : 0;
            vector<vector<int>> roots(m, vector<int>(n, 0));
            int cid = 1 /*component id*/, ans = 0;
            vector<int> ufs = {0}; //union-find set
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(grid[i][j] == '1'){
                        //only need to check left and up nb so that each nb pair is checked only once
                        ufs.push_back(cid);
                        ans++;
                        roots[i][j] = cid;
                        vector<int> nbSet;
                        if(i && grid[i-1][j] == '1')
                            nbSet.push_back(find(ufs, roots[i-1][j]));
                        if(j && grid[i][j-1] == '1'){
                            int up = find(ufs, roots[i][j-1]);
                            if(nbSet.empty() || nbSet[0] != up) //no need to count again for common root
                                nbSet.push_back(up); 
                        }
                        ans -= nbSet.size(); //size could be 0, 1 or 2
                        cid++; //update cid to next available value
                        //union
                        if(nbSet.size()){
                            ufs[roots[i][j]] = nbSet[0];
                            if(nbSet.size() > 1)
                                ufs[nbSet[1]] = nbSet[0];
                        }
                    }
                }
            }
            return ans;
        }
        int find(vector<int>& ufs, int i){
            if(ufs[i]== i) return i;
            else return ufs[i] = find(ufs, ufs[i]); //find root with path compression
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.