Using weighted quick-union and path compression O(klogmn)


  • 1
    P

    Please read this document first. After the reading you would have full understanding of union find algorithm
    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> roots(m*n,-1);
            vector<int> sz(m*n,1);
            vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
            vector<int> res;
            int cnt = 0;
            for(int i=0;i<positions.size();i++){
                int id1 = positions[i].first*n + positions[i].second;
                roots[id1] = id1;
                cnt++;
                for(int j=0;j<dir.size();j++){
                    int y = positions[i].first  + dir[j][0];
                    int x = positions[i].second + dir[j][1];
                    int id2 = y*n+x;
                    if(x>=0 && x<n && y>=0 && y<m && roots[id2] !=-1){
                        unite(roots,sz,findRoot(roots, id2),findRoot(roots, id1),cnt);
                    }
                }
                res.push_back(cnt);
            }
            return res;
        }
        int findRoot(vector<int> & roots, int id){
            while(roots[id]!= id){
               //pass compression
                roots[id] = roots[roots[id]];
                id = roots[id];
            }
            return id;
        }
        void unite(vector<int> &roots, vector<int> &sz, int root1, int root2,int &cnt){
            if(root1!=root2) cnt--;
            //weighted quick_union
            if(sz[root1]<sz[root2]){
                sz[root2]+=sz[root1];
                roots[root1] = root2;
            }else{
                sz[root1]+=sz[root2];
                roots[root2] = root1;
            }
        }
    };
    

  • 0

    @primbo amazing link and implementation.


Log in to reply
 

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