net.cscott.jutil
public class DisjointSet<E> extends Object
DisjointSet is an implementation of disjoint-set forests
using the path compression and union-by-rank heuristics to achieve
O(m * alpha(m, n)) runtime, where 'm' is the total number of
operations, 'n' is the total number of elements in the set, and
'alpha' denotes the *extremely* slowly-growing inverse Ackermann
function.
Version: $Id: DisjointSet.java,v 1.2 2004/01/13 21:40:19 cananian Exp $
| Constructor Summary | |
|---|---|
| DisjointSet() Creates a DisjointSet. | |
| Method Summary | |
|---|---|
| Map<E,E> | asMap() Returns an unmodifiable Map view of the disjoint
set, where every element is mapped to its canonical representative. |
| boolean | contains(Object o) Determines if there is a set of more than one element containing
o. |
| E | find(E o) Returns the representative of the (unique) set containing
o. |
| static void | main(String[] args) Self-test method. |
| String | toString() Returns a human-readable representation of the DisjointSet. |
| void | union(E o1, E o2) Unites the dynamic sets that contain o1 and
o2, say S1 and S2, into a new set that is the
union of these two sets. |
DisjointSet.Map view of the disjoint
set, where every element is mapped to its canonical representative.o.o.o1 and
o2, say S1 and S2, into a new set that is the
union of these two sets. The two sets are assumed to be
disjoint prior to the operation. The representative of the
resulting set is the representative of either S1 or S2; if
both S1 and S2 were previously singletons, the representative
of S1 union S2 is the representative of S2.