C++ standard union find with path compression beat 84.66%


  • 0
    Y

    For details of union find, please refer to https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    class Solution {
    public:
        vector<int> id;
        
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> res;
            int cnt = 0;
            
            id = vector<int>(m * n, -1);
            for (int i = 0; i < positions.size(); i++) {
                int idx = positions[i].first * n + positions[i].second;
                if (id[idx] != -1) continue;
                
                id[idx] = idx;
                cnt++;
                
                int top = idx - n;
                if (top >= 0 && id[top] != -1) {
                    unite(idx, top);
                    cnt--;
                }
                
                int bottom = idx + n;
                if (bottom < m * n && id[bottom] != -1 && !find(idx, bottom)) {
                    unite(idx, bottom);
                    cnt--;
                }
                
                if (positions[i].second > 0) {
                    int left = idx - 1;
                    if (id[left] != -1 && !find(idx, left)) {
                        unite(idx, left);
                        cnt--;
                    }
                }
                
                if (positions[i].second < n - 1) {
                    int right = idx + 1;
                    if (id[right] != -1 && !find(idx, right)) {
                        unite(idx, right);
                        cnt--;
                    }
                }
                
                res.push_back(cnt);
            }
            
            return res;
        }
        
        int root(int i) {
            while (i != id[i]) {
                id[i] = id[id[i]]; // path compression
                i = id[i];
            }
            return i;
        }
        
        bool find(int p, int q) {
            return root(p) == root(q);
        }
        
        void unite(int p, int q) {
            int i = root(p);
            int j = root(q);
            id[i] = j;
        }
    };
    

Log in to reply
 

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