> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/data-structure/union-find/number-of-connected-components-in-an-undirected-graph.md).

# 323. Number of Connected Components in an Undirected 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](/lc/data-structure/union-find/graph-valid-tree.md)

**Code:**

```cpp
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):**

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