<jupyter_start><jupyter_text>Disjoint sets<jupyter_code>!git clone https://github.com/lmcanavals/algorithmic_complexity.git
from algorithmic_complexity.aclib.ds import ds2gv<jupyter_output><empty_output><jupyter_text>Quick union<jupyter_code>class DisjointSet:
  def __init__(self, n):
    self.s = [-1]*n

  def find(self, e):
    if self.s[e] < 0:
      return e
    else:
      ancestor = self.find(self.s[e])
      self.s[e] = ancestor
      return ancestor

  def union(self, a, b):
    A = self.find(a)
    B = self.find(b)
    if A != B:
      if abs(self.s[B]) > abs(self.s[A]):
        self.s[B] += self.s[A]
        self.s[A] = B
      else:
        self.s[A] += self.s[B]
        self.s[B] = A
ds = DisjointSet(8)
print(ds.s)
print(ds.find(5))
print(ds.find(7))
ds2gv(ds)
ds.union(5, 7)
print(ds.s)
print(ds.find(5))
print(ds.find(7))
ds2gv(ds)
ds.union(2, 4)
print(ds.s)
ds2gv(ds)
ds.union(4, 7)
print(ds.s)
ds2gv(ds)
ds.union(3, 0)
print(ds.s)
ds2gv(ds)
ds.union(2, 7)
print(ds.s)
ds2gv(ds)
ds.union(1, 0)
print(ds.s)
ds2gv(ds)
ds.union(3, 5)
print(ds.s)
ds2gv(ds)
ds.union(6, 7)
print(ds.s)
ds2gv(ds)
ds2 = DisjointSet(8)
for i in range(1, 8):
  ds2.union(i, 0)

ds2gv(ds2)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18570254724732949, 'fraction_numerical': 0.03368940016433854, 'mean_word_length': 3.5789473684210527, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '92986', 'license': 'CC0-1.0', 'n_tokens_mistral': 610, 'n_tokens_neox': 594, 'n_words': 103, 'path': 'notebooks/bd_disjointset_weigthed_union.ipynb', 'repo_name': 'AgustinAMaita/DataSet', 'size': '1217'}