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

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.

**The Idea:** First build the undirected graph. Then iterate through each possible element in the graph, and perform a DFS if the element has not been visited. Every successive DFS will explore the graph within it's setting and therefore counts as a connected component.

**Complexity:** O(N) time and O(2n) space

```python
class Solution:
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """

        visited = [False for _ in range(0, n)]
        graph = {i: [] for i in range(0, n)}
        for edge in edges:
            graph[edge[0]].append(edge[1])
        for edge in edges:
            graph[edge[1]].append(edge[0])

        def DFS(start):
            if not visited[start]:
                visited[start] = True
                for i in graph[start]:
                    DFS(i)

        count = 0
        for i in range(0, n):
            if not visited[i]:
                DFS(i)
                count += 1

        return count
```