Share my cpp unionfind solution with path compression


  • 0
    W
    class UnionFind {
    public:
        UnionFind(int n) {
            nodes.reserve(n);
            for(int i = 0; i < n; i++)
                nodes.push_back(node(i));
            count = n;
        }
        
        void unionSets(int idx1, int idx2) {
            int parent1 = findSet(idx1);
            int parent2 = findSet(idx2);
            if(parent1 == parent2)
                return;
            nodes[parent2].parent = &nodes[parent1];
            count--;
        }
        
        int findSet(int idx) {
            struct node* cur = &nodes[idx];
            while(cur -> parent)
                cur = cur -> parent;
            struct node* root = cur;
            cur = &nodes[idx];
            while(cur != root) {
                struct node* next = cur -> parent;
                cur -> parent = root;
                cur = next;
            }
            return root -> num;
        }
        
        int countOfSets() {
            return count;
        }
        
    private:
        struct node {
                int num;
                node* parent;
                node(int n) : num(n), parent(NULL) {}
        };
        
        vector<node> nodes;
        int count;
    };
    
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> res;
            vector<vector<bool> > map(m, vector<bool>(n, false));
            int totalArea = m * n;
            int landArea = 0;
            UnionFind unionFind(m * n);
            auto getIdx = [n](int i, int j) {return n * i + j;};
            for(pair<int, int> pos : positions) {
    			int i = pos.first, j = pos.second;
                if(map[i][j])
                    continue;
                map[i][j] = true;
                landArea++;
                if(i > 0 && map[i - 1][j])
                    unionFind.unionSets(getIdx(i, j), getIdx(i - 1, j));
                if(j > 0 && map[i][j - 1])
                    unionFind.unionSets(getIdx(i, j), getIdx(i, j - 1));
                if(i  < m - 1 && map[i + 1][j])
                    unionFind.unionSets(getIdx(i, j), getIdx(i + 1, j));
                if(j < n - 1 && map[i][j + 1])
                    unionFind.unionSets(getIdx(i, j), getIdx(i, j + 1));
                res.push_back(unionFind.countOfSets() - totalArea + landArea);
            }
            return res;
        }
        
    
    };

Log in to reply
 

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