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

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

找連接圖，用DFS

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]]))

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)