Number of connected components in an undirected graph#

Levels: level-5

Data structures: graph

Description#

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.

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.

Examples#

text

1
2     0          3
3     |          |
4     1 --- 2    4
5
6Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

text

1     0           4
2     |           |
3     1 --- 2 --- 3
4
5Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Python Solution#

 1class Solution(object):
 2    def countComponents(self, n, edges):
 3        """
 4        :type n: int
 5        :type edges: List[List[int]]
 6        :rtype: int
 7        """
 8        V = [[] for _ in range(n)]
 9        for e in edges:
10            V[e[0]].append(e[1])
11            V[e[1]].append(e[0])
12
13        visited = [False for _ in range(n)]
14        cnt = 0
15        for v in range(n):
16            if not visited[v]:
17                cnt += 1
18                self.dfs(V, v, visited)
19
20        return cnt
21
22    def dfs(self, V, v, visited):
23        visited[v] = True
24        for nbr in V[v]:
25            if not visited[nbr]:
26                self.dfs(V, nbr, visited)