All Packages Class Hierarchy This Package Previous Next Index
Class structure.UnionFind
java.lang.Object

+structure.UnionFind
 public class UnionFind
 extends Object
An implementation of a unionfind structure.
The universe consists of a number of values between 0 and n1
These elements, initially, are all in their own set, labeled 0..n1
respectively. Sets may be unioned. The resulting set takes on
the identity of one of the two originals. In addition, the
elements may be found in a set  the result is the integerlabel
of the set containing the element.

UnionFind(int)
 Construct a unionfind set with elementCount elements.

find(int)
 Find the number of the set containing the desired element.

toString()
 Construct a string representation of the unionfind universe.

union(int, int)
 Merge sets containing elements i and j.
UnionFind
public UnionFind(int elementCount)
 Construct a unionfind set with elementCount elements.
 Precondition:
 elementCount >= 0
 Postcondition:
 constructs elementCount disjoint sets labeled 0..elementCount1
 Parameters:
 elementCount  The number of elements in the universe.
find
public int find(int i)
 Find the number of the set containing the desired element.
 Precondition:
 0 <= i < elementCount
 Postcondition:
 returns the index or name of the set containing i
 Parameters:
 i  The element index.
 Returns:
 The index of the set.
union
public int union(int i,
int j)
 Merge sets containing elements i and j.
The identity of the ultimate set is the identity of one of
the (possibly) two sets that contained i and j.
 Precondition:
 0 <= i,j < elementCount
 Postcondition:
 merges sets containing i and j, and returns new set name.
 Parameters:
 i  An element identifying one set.
 j  An element identifying another set.
 Returns:
 The index of the set that is the union of the two sets containing i and j.
toString
public String toString()
 Construct a string representation of the unionfind universe.
 Postcondition:
 returns string representation of sets
 Returns:
 A string representing the sets in the unionfind structure.
 Overrides:
 toString in class Object
All Packages Class Hierarchy This Package Previous Next Index