weiss.nonstandard
Class DisjointSetsFast

java.lang.Object
  weiss.nonstandard.DisjointSetsFast

public class DisjointSetsFast
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

DisjointSetsFast(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

Constructor Detail

DisjointSetsFast

public DisjointSetsFast(int numElements)

Construct the disjoint sets object.

Parameters:

numElements - the initial number of disjoint sets.

Method Detail

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)