weiss.nonstandard
Class DisjointSets
java.lang.Object
|
+--weiss.nonstandard.DisjointSets
- public class DisjointSets
- extends java.lang.Object
Disjoint set class, using union by rank
and path compression.
Elements in the set are numbered starting at 0.
Constructor Summary |
DisjointSets(int numElements)
Construct the disjoint sets object. |
Method Summary |
int |
find(int x)
Perform a find with path compression. |
static void |
main(java.lang.String[] args)
|
void |
union(int root1,
int root2)
Union two disjoint sets using the height heuristic. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
DisjointSets
public DisjointSets(int numElements)
- Construct the disjoint sets object.
- Parameters:
numElements
- the initial number of disjoint sets.
union
public void union(int root1,
int root2)
- Union two disjoint sets using the height heuristic.
root1 and root2 are distinct and represent set names.
- Parameters:
root1
- the root of set 1.root2
- the root of set 2.- Throws:
java.lang.IllegalArgumentException
- if root1 or root2
are not distinct roots.
find
public int find(int x)
- Perform a find with path compression.
- Parameters:
x
- the element being searched for.- Returns:
- the set containing x.
- Throws:
java.lang.IllegalArgumentException
- if x is not valid.
main
public static void main(java.lang.String[] args)