You have a graph of
n nodes. You are given an integer
n and an array
edges[i] = [ai, bi] indicates that there is an edge between
bi in the graph.
Return the number of connected components in the graph.
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1
1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
- There are no repeated edges.
Build an adjacency list representing the relationship between vertices and edges. Then conduct depth first search to count then number of components.
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].append(edge) adjacency_list[edge].append(edge) 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.