Advertisement
Guest User

Untitled

a guest
Dec 11th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.05 KB | None | 0 0
  1. def check_edge(a, b, components):
  2.  
  3. for component in components:
  4. if a in component or b in component:
  5. component.add(a)
  6. component.add(b)
  7. return
  8.  
  9. components.append({a, b})
  10.  
  11. n, m = list(map(int, input().split()))
  12.  
  13. components = []
  14.  
  15. vertices_to_be_processed = {i for i in range(1, n + 1)}
  16.  
  17. for i in range(0, m):
  18. a, b = list(map(int, input().split()))
  19.  
  20. check_edge(a, b, components)
  21.  
  22. vertices_to_be_processed.discard(a)
  23. vertices_to_be_processed.discard(b)
  24.  
  25. for vertex in vertices_to_be_processed:
  26. components.append({vertex})
  27.  
  28. flag = True
  29. while flag:
  30. flag = False
  31. l = len(components)
  32. i = 0
  33. while i < l - 1:
  34. if set.intersection(components[i], components[i+1]):
  35. l -= 1
  36. components[i] = set.union(components[i], components[i+1])
  37. del components[i+1]
  38. flag = True
  39. else:
  40. i += 1
  41.  
  42. print(len(components))
  43.  
  44. for component in components:
  45. print(len(component))
  46. print(*component)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement