util.disjointset

Class OptimalUnionFind

java.lang.Object

util.disjointset.OptimalUnionFind

All Implemented Interfaces:

DisjointSet

public class OptimalUnionFind
extends java.lang.Object
implements DisjointSet

Provides an implementation of the DisjointSet interface. All operations run in near-constant-time (bounded by the inverse Ackermann function)

Constructor Summary

Constructors

Constructor and Description
OptimalUnionFind(int size) Creates a new OptimalUnionFind data structure of the specified size

Method Summary

Modifier and Type	Method and Description
int	distinct() Returns the number of distinct sets.
int	find(int i) Returns a representative member of the set that i is part of.
int	size() Returns the number of elements.
void	union(int i, int j) Unions the two sets specified by i and j.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

OptimalUnionFind

public OptimalUnionFind(int size)

Creates a new OptimalUnionFind data structure of the specified size

Parameters:

size - the size of the OptimalUnionFind data structure

Method Detail

distinct

public int distinct()

Description copied from interface: DisjointSet

Returns the number of distinct sets.

Specified by:

distinct in interface DisjointSet

Returns:

the number of distinct sets

size

public int size()

Description copied from interface: DisjointSet

Returns the number of elements.

Specified by:

size in interface DisjointSet

Returns:

the number of elements

find

public int find(int i)

Description copied from interface: DisjointSet

Returns a representative member of the set that i is part of. This representative member is the same for all members of the same set.

Specified by:

find in interface DisjointSet

Parameters:

i - specifies the set of which we want to find the representative member

Returns:

returns the representative member of the set that i is part of

union

public void union(int i,
                  int j)

Description copied from interface: DisjointSet

Unions the two sets specified by i and j. All elements in the sets of i and j will be represented by the same element.

Specified by:

union in interface DisjointSet

Parameters:

i - member of the first set

j - member of the second set