C++ Solution with union-find


  • 0
    J
        int find(vector<int>& parent, int n) {
        if(parent[n] == -1) return n;
        return parent[n] = find(parent, parent[n]);
    }
    
    void merge(vector<int>& parent, vector<int>& rank, int e1, int e2) {
        int u = find(parent, e1);
        int v = find(parent, e2);
        
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }
    
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<int> parent(n, -1);
        vector<int> rank(n, 1);
        
        for(int i = 0; i<edges.size(); i++) 
            merge(parent, rank, edges[i].first, edges[i].second);
            
        unordered_set<int> hset;
        for(int i = 0; i<parent.size(); i++) {
            hset.insert(find(parent, i));
        }
    
        return hset.size();
    }

Log in to reply
 

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