> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/323.-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:**

```
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2
```

**Example 2:**

```
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

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

Output:  1
```

**Note:**\
You can assume that no duplicate edges will appear in `edges`. Since all edges are undirected, `[0, 1]` is the same as `[1, 0]` and thus will not appear together in `edges`.

{% hint style="info" %}
建立roots array 來代表i屬於group roots\[i]，利用union-find來合併edge上兩端的節點，若edge上兩個節點所屬的group不同，那就將他們合併為同一個group，每合併一次就減少總group數量。
{% endhint %}

```cpp
// Union Find
int getRoot(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = getRoot(roots, roots[i]);
}
int countComponents(int n, vector<vector<int>>& edges) { // time: O(E * log*(n)); space: O(n)
    int res = n;
    vector<int> roots(n), size(n, 1);
    for (int i = 0; i < n; ++i) roots[i] = i;
    for (auto edge : edges) {
        int r1 = getRoot(roots, edge[0]);
        int r2 = getRoot(roots, edge[1]);
        if (r1 != r2) {
            if (size[r1] >= size[r2]) {
                roots[r2] = r1;
                size[r1] += size[r2];
            } else {
                roots[r1] = r2;
                size[r2] += size[r1];
            }
            --res;
        }
    }
    return res;
}
```

{% hint style="info" %}
根據edges建立adjacency list，DFS搭配visited array來記錄是否已經掃描過該節點。
{% endhint %}

```cpp
// DFS + adjacency list
void dfs(vector<vector<int> >& graph, vector<bool>& visited, int i) {
    if (visited[i]) return;
    visited[i] = true;
    for (int j = 0; j < graph[i].size(); ++j) {
        dfs(graph, visited, graph[i][j]);
    }
}
int countComponents(int n, vector<vector<int>>& edges) { // time: O(n + E); space: (n + E)
    int res = 0;
    vector<vector<int> > graph(n); // adjacency list
    vector<bool> visited(n, false);
    // build graph
    for (vector<int>& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    // DFS
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            ++res;
        }
    }
    return res;
}
```

{% hint style="info" %}
根據edges建立adjacency list，BFS搭配visited array來紀錄是否已經掃描過該節點。
{% endhint %}

```cpp
// BFS + adjacency list
int countComponents(int n, vector<vector<int>>& edges) { // time: O(E + n); space: O(E + n)
    vector<vector<int> > graph(n); // adjacency list
    vector<bool> visited(n, false);
    // build graph
    for (vector<int>& edge : edges) { // time: O(E)
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    int res = 0;
    // BFS
    for (int i = 0; i < n; ++i) { // time: O(n)
        if (!visited[i]) {
            ++res;
            queue<int> q({i});
            while (!q.empty()) {
                int index = q.front(); q.pop();
                visited[index] = true;
                for (int neighbor : graph[index]) {
                    if (!visited[neighbor]) q.push(neighbor);
                }
            }
        }
    }
    return res;
}
```