Clean and easy C++ union-find solution 13ms


  • 0
    W
    class Solution {
    public:
        int find(int x) {
            if (father[x] == x) {
                return x;
            }
            return father[x] = find(father[x]);
        }
        
        void connect(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }
    
        int countComponents(int n, vector<pair<int, int>>& edges) {
            father.resize(n);
            count = n;
            
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
            
            for (auto e : edges) {
                connect(e.first, e.second);
            }
            
            return count;
        }
        
    private:
        vector<int> father;
        int count;
    };
    
    

Log in to reply
 

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