smj007

Number of connected components in a graph

Jul 30th, 2025
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.62 KB | None | 0 0
  1. class Solution:
  2.     def countComponents(self, n: int, edges: List[List[int]]) -> int:
  3.        
  4.  
  5.         def dfs(node: int) -> None:
  6.             if node in visited:
  7.                 return
  8.  
  9.             visited.add(node)
  10.  
  11.             for nb in hashmap[node]:
  12.                 dfs(nb)
  13.  
  14.  
  15.         hashmap = defaultdict(list)
  16.         for e in edges:
  17.             a, b = e
  18.             hashmap[a].append(b)
  19.             hashmap[b].append(a)
  20.  
  21.         visited = set()
  22.         count = 0
  23.  
  24.         for i in range(n):
  25.             if i not in visited:
  26.                 dfs(i)
  27.                 count += 1
  28.  
  29.         return count
  30.  
Advertisement
Add Comment
Please, Sign In to add comment