Advertisement
serega1112

Connected components

Feb 17th, 2022
775
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.57 KB | None | 0 0
  1. from collections import defaultdict
  2.  
  3. n, m = map(int, input().split())
  4. g = defaultdict(list)
  5. for _ in range(m):
  6.     a, b = map(int, input().split())
  7.     g[a].append(b)
  8.     g[b].append(a)
  9.  
  10. comps = []
  11. visited = set()
  12.  
  13.  
  14. def dfs(node):
  15.     if node not in visited:
  16.         visited.add(node)
  17.         comps[-1].append(node)
  18.         for neigh in g[node]:
  19.             dfs(neigh)
  20.  
  21. for v in range(1, n+1):
  22.     if v not in visited:
  23.         comps.append([])
  24.         dfs(v)
  25.  
  26. print(len(comps))
  27. for c in comps:
  28.     print(len(c))
  29.     print(' '.join([str(i) for i in c]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement