Advertisement
serega1112

Connected components

Mar 6th, 2021
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.72 KB | None | 0 0
  1.  
  2. n, m = map(int, input().split())
  3.  
  4. edges = []
  5. while m:
  6.     edges.append(list(map(int, input().split())))
  7.     m -= 1
  8.  
  9. g = dict()
  10.  
  11. for v in range(1, n + 1):
  12.     g[v] = []
  13.  
  14. for a, b in edges:
  15.     g[a].append(b)
  16.     g[b].append(a)
  17.  
  18. count = 0
  19. visited = set()
  20. res = []
  21.  
  22. for v in g:
  23.     if v not in visited:
  24.         comp = []
  25.         count += 1
  26.         st = [v]
  27.         visited.add(v)    
  28.         while st:
  29.             cur = st.pop()
  30.             comp.append(str(cur))
  31.             for nb in g[cur]:
  32.                 if nb not in visited:
  33.                     st.append(nb)
  34.                     visited.add(nb)
  35.         res.append(comp)
  36. print(count)
  37. for comp in res:
  38.     print(len(comp))
  39.     print(' '.join(comp))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement