fork download
copy 
  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
comments (?)
stdin
copy 
2
4
2
0 1
1 2
3
0
stdout
copy 
2
3
https://ideone.com/E6WFux
language:
Python (cpython 2.7.16)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!