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] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
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 <= 20001 <= edges.length <= 5000edges[i].length == 20 <= ai <= bi < nai != bi- 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.