Skip to content

Instantly share code, notes, and snippets.

@bumfo bumfo/merge_non_disjoint_sets.py Secret
Last active Mar 13, 2019

Embed
What would you like to do?
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')]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.