chc.util.UnionFind module
Union-find data structure
Union-find data structure. Based on Josiah Carlson’s code, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912 with significant additional changes by D. Eppstein.
- class chc.util.UnionFind.UnionFind[source]
Bases:
Generic[chc.util.UnionFind.T]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.