Skip to content

Instantly share code, notes, and snippets.

@whilefalse
Created August 24, 2009 12:19
Show Gist options
  • Save whilefalse/173846 to your computer and use it in GitHub Desktop.
Save whilefalse/173846 to your computer and use it in GitHub Desktop.
Simple implementation of union-find for arbitrary objects in Python
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