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
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
Last modified 4yr ago