C++ 14 lines clean solution using weighted union find with comments


  • 0

    My solution used weighted union find and path compression.
    Weight is to record the each node's number of child nodes.

    int countComponents(int n, vector<pair<int, int>>& edges) {
            int index[n], weight[n];                                            // weighted index for union find
            for (int i = 0; i < n; i ++) { index[i] = i, weight[i] = 1; }       // initialize index and weight
            
            for (auto p : edges) {
                int a = p.first, b = p.second;
                while (index[a] != a) { a = index[a] = index[index[a]]; }       // find parent with path compression
                while (index[b] != b) { b = index[b] = index[index[b]]; }       // find parent with path compression
                
                if (a != b) {
                    if (weight[a] < weight[b]) { swap(a, b); }                  // make sure a is heavier than b
                    index[b] = a;
                    weight[a] += weight[b];
                    n--;                                                        // union a and b, so decrease n
                }
            }
            
            return n;
    }
    

Log in to reply
 

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