# Number of Connected Components in an Un-directed Graph

Given`n`nodes labeled from`0`to`n - 1`and 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
``````

Given`n = 5`and`edges = [[0, 1], [1, 2], [3, 4]]`, return`2`.

Example 2:

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

Given`n = 5`and`edges = [[0, 1], [1, 2], [2, 3], [3, 4]]`, return`1`.

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;
}
};
``````