C++ Solution using union-find


  • 4
    I

    I used union and find to see each time we add edges, I check if they belong to the same set, if so, we do nothing. Otherwise, I call union that effectively remove one set. Once we are done processing edges, we know that we can subtract the number of union from 'n' value and that is the remaining number of set.

    vector<int> id;
    public:
    int find(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]]; // compression
            i = id[i];
        }
        return i;
    }
    void unions(int p, int q) {
        int x = find(p);
        int y = find(q);
        id[x] = y;
    }
    int countComponents(int n, vector<pair<int, int>>& edges) {
        id.resize(n);
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        int count = 0;
        for (const auto& edge: edges) {
            int x = find(edge.first);
            int y = find(edge.second);
            if (x != y) {
                unions(edge.first, edge.second);
                count++;
            }
        }
        return n-count;
    }

  • 3
    X

    I think you call find twice for each node in a pair, which is not necessary.

    Here is the better code.

    class Solution {
    private:
        vector<int> parents;
        int find(int x) {
            while (x != parents[x]) {
                parents[x] = parents[parents[x]];  // compression
                x = parents[x];
            }
            return x;
        }
        bool unions(int p, int q) {
            int x = find(p);
            int y = find(q);
            if (x != y) {
                parents[x] = y;
                return true;
            }
            return false;
        }
    public:
        int countComponents(int n, vector<pair<int, int>>& edges) {
            parents.resize(n);
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
            int count = n;
            for (const auto& edge: edges) {
                if (unions(edge.first, edge.second)) {  // changed here
                    --count;
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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