fork download
copy 
  1. class DSU:
  2.     def __init__(self, V):
  3.         self.parent = [0] * V
  4.         self.rank = [0] * V
  5.  
  6.         for i in range(V):
  7.             self.make_set(i)
  8.  
  9.     def make_set(self, x):
  10.         self.parent[x] = x
  11.         self.rank[x] = 0
  12.  
  13.     def find_set(self, x):
  14.         if self.parent[x] == x:
  15.             return x
  16.         else:
  17.             rep_x = self.find_set(self.parent[x])
  18.             self.parent[x] = rep_x # Path Compression
  19.             return rep_x
  20.  
  21.     def union(self, u, v):
  22.         rep_u = self.find_set(u)
  23.         rep_v = self.find_set(v)
  24.  
  25.         if rep_u != rep_v:
  26.             # Union By Rank
  27.             if self.rank[rep_u] > self.rank[rep_v]:
  28.                 self.parent[rep_v] = rep_u
  29.             elif self.rank[rep_v] > self.rank[rep_u]:
  30.                 self.parent[rep_u] = rep_v
  31.             else:
  32.                 self.parent[rep_v] = rep_u
  33.                 self.rank[rep_u] += 1
  34.  
  35.     def same_set(self, u, v):
  36.         rep_u = self.find_set(u)
  37.         rep_v = self.find_set(v)
  38.  
  39.         if rep_u == rep_v:
  40.             return True
  41.         else:
  42.             return False
  43.  
  44. dsu = DSU(5)
  45.  
  46. dsu.union(0, 2)
  47.  
  48.  
  49. print(dsu.same_set(0, 2))
  50.  
  51.  
  52.  
Success #stdin #stdout 0.07s 14088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
True
https://ideone.com/n5STrm
language:
Python 3 (python  3.12)
created:
1 day 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!