Skip to content

Instantly share code, notes, and snippets.

@Sushant
Forked from whilefalse/Python Union-Find
Last active August 29, 2015 14:10
Show Gist options
  • Save Sushant/5f383643bc86bb69cd8f to your computer and use it in GitHub Desktop.
Save Sushant/5f383643bc86bb69cd8f to your computer and use it in GitHub Desktop.
def union(parent,child):
"""Performs a union by attaching the root node of the smaller set to the
root node of the larger set"""
if parent.set_size < child.set_size:
child, parent = parent, child
parent_head = find(parent)
child_head = find(child)
if parent_head == child_head:
return
child_head.parent = parent_head
parent_head.set_size = parent_head.set_size + child_head.set_size
def find(item):
"""Finds the root node of a given item, attaching it directly to its root node
on the way up"""
if item.parent == item:
return item
else:
item.parent = find(item.parent)
return item.parent
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment