# Number of Connected Components in an Undirected Graph

##### January 6, 2024

## Problem #

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: #

```
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: There are two connected components: 0-1-2 and 3-4.
```

### Solution #

**Algorithm: Depth-First Search (DFS)**

The idea is to use DFS to explore each node and mark all nodes in the same connected component as visited. The number of times a new DFS is initiated gives the number of connected components.

### Algorithm Steps: #

**Create an Adjacency List**: Represent the graph using an adjacency list.**DFS Traversal**: For each unvisited node, perform a DFS traversal and mark all reachable nodes as visited.**Count Connected Components**: Each time a new DFS starts, increment the count of connected components.

### Python Code #

```
def countComponents(n, edges):
def dfs(node):
if visited[node]:
return
visited[node] = True
for neighbor in adj_list[node]:
dfs(neighbor)
# Create an adjacency list
adj_list = {i: [] for i in range(n)}
for edge in edges:
adj_list[edge[0]].append(edge[1])
adj_list[edge[1]].append(edge[0])
visited = [False] * n
count = 0
for i in range(n):
if not visited[i]:
dfs(i)
count += 1
return count
# Example Usage
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(countComponents(n, edges))
# Output: 2
```

### Time Complexity: #

**O(V + E)**: Where V is the number of vertices and E is the number of edges. The adjacency list is traversed completely.

### Space Complexity: #

**O(V + E)**: Space for the adjacency list and the visited array.