merge_non_disjoint_sets.py

merge_non_disjoint_sets.py

from array import array

def merge_non_disjoint_sets(sets):
  n = 0
  s = dict()
  r = list()

  for a in sets:
    for b in a:
      if b not in s:
        s[b] = n
        r.append(b)
        n += 1

  P = array('i', (i for i in range(0, n)))

  def find(i):
    if i == P[i]: return i
    P[i] = find(P[i])
    return P[i]

  def merge(i, j):
    P[find(j)] = find(i)

  for a in sets:
    if a:
      it = iter(a)
      i = s[next(it)]

      for x in it:
        j = s[x]
        merge(i, j)
  
  for i in range(0, n):
    find(i)

  Q = dict()
  R = []
  for i in P:
    if i not in Q:
      l = []
      Q[i] = l
      R.append(l)

  for i in range(0, n):
    j = P[i]
    Q[j].append(r[i])

  return [tuple(x) for x in R]
  

y = merge_non_disjoint_sets([('A', 'B'), ('B', 'C'), ('X', 'Y')])

print(y)  # [('A', 'B', 'C'), ('X', 'Y')]