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