This is a place to put my clutters, no matter you like it or not, welcome here.
0%
323. Number of Connected Components in an Undirected Graph
Posted onEdited onIn面試Views: Symbols count in article: 983Reading time ≈1 mins.
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
1 2 3 4 5 6 7
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3 | | 1 --- 2 4
Output: 2
Example 2
1 2 3 4 5 6 7
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
T:Build graph will take O(n) and traversal all number will take O(n) S:O(n) from typing import List import collections class Solution(): def countComponents(self, n: int, edges: List[List[int]]) -> int: dist = collections.defaultdict(list) for source, target in edges: dist[source].append(target) dist[target].append(source) count = 0 visited=set() queue = collections.deque() for x in range(n): if x in visited: continue queue.append(x) while queue: source=queue.popleft() if source in visited: continue visited.add(source) for target in dist[source]: queue.append(target) count+=1 return count print(Solution().countComponents(5,[[0,1],[1,2],[3,4]]))