Class QuickFindUF

java.lang.Object

QuickFindUF

public class QuickFindUF
extends java.lang.Object

The QuickFindUF class represents a union-find data structure. It supports the union and find operations, along with methods for determinig whether two objects are in the same component and the total number of components.

This implementation uses quick find. Initializing a data structure with N objects takes linear time. Afterwards, find, connected, and count takes constant time but union takes linear time.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
QuickFindUF(int N) Initializes an empty union-find data structure with N isolated components 0 through N-1.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	connected(int p, int q) Are the two objects p and q in the same component?
int	count() Return the number of components.
int	find(int p) Return the component identifier for the component containing object p.
static void	main(java.lang.String[] args) Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, where each integer represents some object; if the objects are in different components, merge the two components and print the pair to standard output.
void	union(int p, int q) Merge components containing p and q.

Methods inherited from class java.lang.Object

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

Constructor Detail

QuickFindUF

public QuickFindUF(int N)

Initializes an empty union-find data structure with N isolated components 0 through N-1.

Parameters:

N - the number of objects

Throws:

java.lang.IllegalArgumentException - if N < 0

Method Detail

count

public int count()

Return the number of components.

Returns:

the number of components (between 1 and N)

find

public int find(int p)

Return the component identifier for the component containing object p.

Parameters:

p - the integer representing one object

Returns:

the component identifier for the component containing object p

Throws:

java.lang.IndexOutOfBoundsException - unless 0 <= p < N

connected

public boolean connected(int p,
                int q)

Are the two objects p and q in the same component?

Parameters:

p - the integer representing one object

q - the integer representing the other object

Returns:

true if the objects p and q are in the same component; false otherwise

Throws:

java.lang.IndexOutOfBoundsException - unless both 0 <= p < N and 0 <= q < N

union

public void union(int p,
         int q)

Merge components containing p and q.

Parameters:

p - the integer representing one object

q - the integer representing the other object

Throws:

java.lang.IndexOutOfBoundsException - unless both 0 <= p < N and 0 <= q < N

main

public static void main(java.lang.String[] args)

Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, where each integer represents some object; if the objects are in different components, merge the two components and print the pair to standard output.