Skip to content

Instantly share code, notes, and snippets.

View SofiaGodovykh's full-sized avatar

Sofia SofiaGodovykh

  • San Francisco, CA
View GitHub Profile
@tnoda
tnoda / union_find.py
Created June 24, 2014 08:34
Union-Find in Python
class UnionFind:
"""Weighted quick-union with path compression.
The original Java implementation is introduced at
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
>>> uf = UnionFind(10)
>>> for (p, q) in [(3, 4), (4, 9), (8, 0), (2, 3), (5, 6), (5, 9),
... (7, 3), (4, 8), (6, 1)]:
... uf.union(p, q)