Last active
February 28, 2020 14:19
-
-
Save haritonch/5415bdc88b5d804a3f4ca4f89f80eeb3 to your computer and use it in GitHub Desktop.
Union Find implementation in Python 3
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
def __init__(self, val): | |
self.value = val | |
self.size = 1 | |
'''size holds the number of a node's offsprings | |
it is used when we apply union | |
''' | |
self.parent = self | |
def find(x): | |
if x.parent != x: | |
x.parent = find(x.parent) | |
''' | |
path compression | |
every node we visit gets adopted by the root of the tree | |
''' | |
return x.parent | |
def union(x, y): | |
xRoot = find(x) | |
yRoot = find(y) | |
if (xRoot == yRoot): | |
pass # x and y already unified, do nothing | |
else: | |
'''if y's tree has more nodes than x's tree then | |
y's tree root becomes x's root's parent | |
we update the number of offspings accordingly | |
''' | |
if xRoot.size <= yRoot.size: | |
xRoot.parent = yRoot | |
yRoot.size += xRoot.size | |
else: | |
yRoot.parent = xRoot | |
xRoot.size += yRoot.size | |
if __name__ == "__main__": | |
# write your code below here and play around | |
x = [makeSet(i) for i in range(10)] | |
for i in range(8): | |
union(x[i], x[i+2]) | |
for i in range(10): | |
print(find(x[i]).value) | |
print('------------------') | |
union(x[0], x[2]) # nothing changes, x[0] and x[2] are in the same set | |
for i in range(10): | |
print(find(x[i]).value) | |
print('------------------') | |
union(x[0], x[1]) # we unify the two sets and now everything is in the same set | |
for i in range(10): | |
print(find(x[i]).value) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment