Skip to content

Instantly share code, notes, and snippets.


bumfo/ Secret

Last active Mar 13, 2019
What would you like to do?
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
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):
Q = dict()
R = []
for i in P:
if i not in Q:
l = []
Q[i] = l
for i in range(0, n):
j = P[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