fork download
  1. import sys
  2.  
  3. class DSU:
  4. def __init__(self, size):
  5. self.parent = list(range(size))
  6. self.rank = [1] * size
  7.  
  8. def find(self, x):
  9. if self.parent[x] != x:
  10. self.parent[x] = self.find(self.parent[x])
  11. return self.parent[x]
  12.  
  13. def union(self, x, y):
  14. x_root = self.find(x)
  15. y_root = self.find(y)
  16. if x_root == y_root:
  17. return False
  18. if self.rank[x_root] < self.rank[y_root]:
  19. self.parent[x_root] = y_root
  20. self.rank[y_root] += self.rank[x_root]
  21. else:
  22. self.parent[y_root] = x_root
  23. self.rank[x_root] += self.rank[y_root]
  24. return True
  25.  
  26. def main():
  27. data = sys.stdin.read().split()
  28. ptr = 0
  29. T = int(data[ptr])
  30. ptr += 1
  31. for _ in range(T):
  32. N = int(data[ptr])
  33. ptr += 1
  34. e = int(data[ptr])
  35. ptr += 1
  36. dsu = DSU(N)
  37. components = N
  38. for __ in range(e):
  39. a = int(data[ptr])
  40. b = int(data[ptr + 1])
  41. ptr += 2
  42. if dsu.union(a, b):
  43. components -= 1
  44. print(components)
  45.  
  46. if __name__ == "__main__":
  47. main()
Success #stdin #stdout 0.02s 7120KB
stdin
2
4
2
0 1
1 2
3
0
stdout
2
3