Skip to content

Instantly share code, notes, and snippets.

@haritonch
Last active February 28, 2020 14:19
Show Gist options
  • Save haritonch/5415bdc88b5d804a3f4ca4f89f80eeb3 to your computer and use it in GitHub Desktop.
Save haritonch/5415bdc88b5d804a3f4ca4f89f80eeb3 to your computer and use it in GitHub Desktop.
Union Find implementation in Python 3
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