## Description

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

You have a graph of `n`

nodes. You are given an integer `n`

and an array `edges`

where `edges[i] = [a`

indicates that there is an edge between _{i}, b_{i}]`a`

and _{i}`b`

in the graph._{i}

Return *the number of connected components in the graph*.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

`1 <= n <= 2000`

`1 <= edges.length <= 5000`

`edges[i].length == 2`

`0 <= a`

_{i}<= b_{i}< n`a`

_{i}!= b_{i}- There are no repeated edges.

## Explanation

Build an adjacency list representing the relationship between vertices and edges. Then conduct depth first search to count then number of components.

## Python Solution

```
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
count = 0
visited = set()
adjacency_list = []
for i in range(n):
adjacency_list.append([])
for edge in edges:
adjacency_list[edge[0]].append(edge[1])
adjacency_list[edge[1]].append(edge[0])
for vertice in range(n):
if vertice not in visited:
self.dfs(vertice, adjacency_list, visited)
count += 1
return count
def dfs(self, vertice, adjacency_list, visited):
visited.add(vertice)
for adj_vertice in adjacency_list[vertice]:
if adj_vertice not in visited:
self.dfs(adj_vertice, adjacency_list, visited)
```

- Time Complexity: O(V + E). V is the number of vertices, E is the number of edges.
- Space Complexity: O(V + E). V is the number of vertices, E is the number of edges.