323. Number of Connected Components in an Undirected Graph

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1.

Thoughts:

1. Connected graph: add new edge to merge (make less) components if no cycle after being added is introduced-> union find: using an array to map each nodes's root value to detect cycle.

2. Time: O(n*len(edges)). space(n)

3. Very similar to 261.Graph Valid Tree

Code:

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        if(n == 0) return n; // need to manually check this case as array length > 0, 
        // which is different from Java
        int res = n; int roots [n];
        for(auto & i: roots) i = -1;

        for(pair<int,int> p : edges){
            int roota = find(roots, p.first);
            int rootb = find(roots, p.second);
            if(roota != rootb) {
                // union
                roots[roota] = rootb;
                res--;
            }
        }

        return res;
    }

    int find(int roots [], int v){
        while(roots[v] != -1) v = roots[v];
        return v;
    }
};

Code (Java):

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        if(n == 0) return n; // need to manually check this case as array length > 0, 
        // which is different from Java
        int res = n; int roots [n], rank[n];
        for(int i = 0 ; i < n; i++) roots[i] = i;

        for(pair<int,int> p : edges){
            int roota = find(roots, p.first);
            int rootb = find(roots, p.second);
            if(roota != rootb) {
                // union by rank
                // if(rank[roota] > rank[rootb]){
                //     roota += rootb;
                //     rootb = roota - rootb;
                //     roota -= rootb;
                // }
                // rank[rootb] += (rank[roota] == rank[rootb]) ?1:0;
                roots[roota] = rootb;
                res--;
            }
        }

        return res;
    }

    int find(int roots [], int v){
        while(roots[v] != v) {
            // path compression
            // roots[v] = roots[roots[v]];
            v = roots[v];
        }
        return v;
    }
};