C++ 13ms 17 lines weighted union find


  • 1
    class Solution {
    private:
        int findParent (int cur, int parent[]) {                            // find parent with path compression
            while (cur != parent[cur])
                cur = parent[cur] = parent[parent[cur]];
            
            return cur;
        }
        
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            int parent[n], weight[n];
            for (int i = 0; i < n; i++) { parent[i] = i, weight[i] = 1; }
            
            for (auto e : edges) {
                int a = findParent(e.first, parent), b = findParent(e.second, parent);
                if (a == b) { 
                    return false;                                           // found loop, return false
                } else { 
                    if (weight[a] < weight[b]) { swap(a, b); }              // always let a to be the heavier one
                    parent[b] = a, weight[a] += weight[b], n--;             // update stats
                }
            }
            
            return n == 1;                                                  // we can only have one parent at last
        }
    };
    

Log in to reply
 

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