edu.princeton.cs.algorithms

Class QuickFindUF

java.lang.Object

edu.princeton.cs.algorithms.QuickFindUF

public class QuickFindUF
extends 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.

Author:

Robert Sedgewick, 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

Modifier and Type	Method and Description
boolean	connected(int p, int q) Are the two sites p and q/tt> in the same component?
int	count() Returns the number of components.
int	find(int p) Returns the component identifier for the component containing site p.
static void	main(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) Merges the component containing sitep with the component containing site 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:

IllegalArgumentException - if N < 0

Method Detail

count

public int count()

Returns the number of components.

Returns:

the number of components (between 1 and N)

find

public int find(int p)

Returns the component identifier for the component containing site p.

Parameters:

p - the integer representing one site

Returns:

the component identifier for the component containing site p

Throws:

IndexOutOfBoundsException - unless 0 <= p < N

connected

public boolean connected(int p,
                         int q)

Are the two sites p and q/tt> in the same component?

Parameters:

p - the integer representing one site

q - the integer representing the other site

Returns:

true if the two sites p and q are in the same component, and false otherwise

Throws:

IndexOutOfBoundsException - unless both 0 <= p < N and 0 <= q < N

union

public void union(int p,
                  int q)

Merges the component containing sitep with the component containing site q.

Parameters:

p - the integer representing one site

q - the integer representing the other site

Throws:

IndexOutOfBoundsException - unless both 0 <= p < N and 0 <= q < N

main

public static void main(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.