UnionFind

class UnionFind

Bases: UnionFind

Union-find data structure.

Each unionFind instance X maintains a family of disjoint sets of hashable objects, supporting the following two methods:

• X[item] returns a name for the set containing the given item. Each set is named by an arbitrarily-chosen one of its members; as long as the set remains unchanged it will keep the same name. If the item is not yet part of a set in X, a new singleton set is created for it.

• X.union(item1, item2, …) merges the sets containing each item into a single larger set. If any item is not yet part of a set in X, it is added to X as one of the members of the merged set.

  Union-find data structure. Based on Josiah Carlson’s code, https://code.activestate.com/recipes/215912/ with significant additional changes by D. Eppstein. http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py

__init__(size)

Create a new empty union-find structure.

If elements is an iterable, this structure will be initialized with the discrete partition on the given set of elements.

Methods

__init__	Create a new empty union-find structure.
find	Find and return the name of the set containing the object.
union	Find the sets containing the objects and merge them all.

Attributes

class_type