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.  
  27.             # UNION BY RANK
  28.  
  29.             if self.rank[rep_u] > self.rank[rep_v]:
  30.                 self.parent[rep_v] = rep_u
  31.             elif self.rank[rep_v] > self.parent[rep_u]:
  32.                 self.parent[rep_u] = rep_v
  33.             else:
  34.                 self.parent[rep_v] = rep_u
  35.                 self.rank[rep_u] += 1
  36.  
  37.     def same_set(self, u, v):
  38.         rep_u = self.find_set(u)
  39.         rep_v = self.find_set(v)
  40.  
  41.         if rep_u == rep_v:
  42.             return True
  43.         else:
  44.             return False
  45.  
  46.  
  47. dsu = DSU(4)
  48. dsu.union(0, 3)
  49. dsu.union(3, 1)
  50. print(dsu.parent)
  51.  
  52. print(dsu.same_set(1, 3))
  53.  
Success #stdin #stdout 0.07s 14080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 0, 2, 0]
True
https://ideone.com/bfzZyW
language:
Python 3 (python  3.12)
created:
3 hours 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!