C++ union find


  • 0
    struct DJSetNode {
        int label;
        int rank;
        DJSetNode* parent;
        DJSetNode(int lb,int r,DJSetNode* p):label(lb),rank(r),parent(p) {}
    };
    
    class Solution {
        unordered_set<DJSetNode*> forest;
        
        DJSetNode* makeNode() {
            DJSetNode* cur = new DJSetNode(0,0,nullptr);
            forest.insert(cur);
            return cur;
        }
        
        DJSetNode* find(DJSetNode* n) {
            if(n==nullptr) return n;
            while(n->parent) {
                n = n->parent;
            }
            return n;
        }
        
        DJSetNode* merge(DJSetNode* n1, DJSetNode* n2) {
            DJSetNode* r1 = find(n1);
            DJSetNode* r2 = find(n2);
            if(r1==r2)  return r1; // same tree
            else if(r1->rank > r2->rank) {
                r2->parent = r1;
                forest.erase(r2);
                return r1;
            } else if(r1->rank < r2->rank) {
                r1->parent = r2;
                forest.erase(r1);
                return r2;
            } else {
                r2->parent = r1;
                forest.erase(r2);
                r1->rank++;
                return r1;
            }
        }
        
        int add(const pair<int,int>& p) {
            vector<DJSetNode*> nbs;
            int x = p.first;
            int y = p.second;
            DJSetNode* cur = makeNode();
            Map[x][y] = cur;
            if(x>0 && Map[x-1][y]) cur = merge(cur,Map[x-1][y]);
            if(y>0 && Map[x][y-1]) cur = merge(cur,Map[x][y-1]);
            if(x<M-1 && Map[x+1][y]) cur = merge(cur,Map[x+1][y]);
            if(y<N-1 && Map[x][y+1]) cur = merge(cur,Map[x][y+1]);
            return forest.size();
        }
        int M,N;
        vector<vector<DJSetNode*>> Map;
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            M = m;
            N = n;
            Map = vector<vector<DJSetNode*>>(m,vector<DJSetNode*>(n,nullptr));
            vector<int> ans;
            for(auto p : positions) {
                ans.push_back(add(p));
            }
            return ans;
        }
    };
    

Log in to reply
 

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