Union-find with path compression C++ solution, 148 ms, beats 100%


  • 0
    J
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> result;
            vector<int> init(n*m, -1);
            nodes_.swap(init);
            const vector<pair<int, int>> extends = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            int count = 0;
            for(auto p:positions){
                const int ind = p.first * n + p.second; 
                if(nodes_[ind]<0){
                    ++count;
                    nodes_[ind] = ind;
                    for(auto& e:extends){
                        const int x = p.first+e.first;
                        const int y = p.second+e.second;
                        const int new_ind = x*n + y;
                        if(x>=0 && x<m && y>=0 && y<n && nodes_[new_ind]>=0){
                            const int root = find(ind);
                            const int new_root = find(new_ind);
                            if(root != new_root){
                                --count;
                               unite(root, new_root);
                            }
                        }
                    }
               }
               result.push_back(count);
           }
           return result;
       }
    private:
       void unite(int p, int q){
           if(p!=q){
               nodes_[q] = p;
           }
       }
    
    //find root
       int find(int id){
           int org = id;
           while(id!=nodes_[id]){
               id = nodes_[nodes_[id]];
           }
           int t = 0;
           for(int i=org; i!=nodes_[i]; i=t){
               t= nodes_[i];
               nodes_[i] = id;
           }
           return id;
       }
        
    private:
        vector<int> nodes_;
    };

Log in to reply
 

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