edu.princeton.cs.algs4

Class QuickFindUF

Object

edu.princeton.cs.algs4.QuickFindUF

public class QuickFindUF
extends Object

The QuickFindUF class represents a union–find data type (also known as the disjoint-sets data type). It supports the classic union and find operations, along with a count operation that returns the total number of sets.

The union–find data type models a collection of sets containing n elements, with each element in exactly one set. The elements are named 0 through n–1. Initially, there are n sets, with each element in its own set. The canonical element of a set (also known as the root, identifier, leader, or set representative) is one distinguished element in the set. Here is a summary of the operations:

• find(p) returns the canonical element of the set containing p. The find operation returns the same value for two elements if and only if they are in the same set.
• union(p, q) merges the set containing element p with the set containing element q. That is, if p and q are in different sets, replace these two sets with a new set that is the union of the two.
• count() returns the number of sets.

The canonical element of a set can change only when the set itself changes during a call to union—it cannot change during a call to either find or count.

This implementation uses quick find. The constructor takes Θ(n) time, where n is the number of sites. The find, connected, and count operations take Θ(1) time; the union operation takes Θ(n) time.

For alternative implementations of the same API, see UF, QuickUnionUF, and WeightedQuickUnionUF. 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 elements 0 through n-1.

Method Summary

Modifier and Type	Method and Description
boolean	connected(int p, int q) Deprecated. Replace with two calls to find(int).
int	count() Returns the number of sets.
int	find(int p) Returns the canonical element of the set containing element p.
static void	main(String[] args) Reads an integer n and a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer in the pair represents some element; if the elements are in different sets, merge the two sets and print the pair to standard output.
void	union(int p, int q) Merges the set containing element p with the set containing element q.

Methods inherited from class 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 elements 0 through n-1. Initially, each element is in its own set.

Parameters:

n - the number of elements

Throws:

IllegalArgumentException - if n < 0

Method Detail

count

public int count()

Returns the number of sets.

Returns:

the number of sets (between 1 and n)

find

public int find(int p)

Returns the canonical element of the set containing element p.

Parameters:

p - an element

Returns:

the canonical element of the set containing p

Throws:

IllegalArgumentException - unless 0 <= p < n

connected

@Deprecated
public boolean connected(int p,
                                     int q)

Deprecated. Replace with two calls to find(int).

Returns true if the two elements are in the same set.

Parameters:

p - one element

q - the other element

Returns:

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

Throws:

IllegalArgumentException - unless both 0 <= p < n and 0 <= q < n

union

public void union(int p,
                  int q)

Merges the set containing element p with the set containing element q.

Parameters:

p - one element

q - the other element

Throws:

IllegalArgumentException - unless both 0 <= p < n and 0 <= q < n

main

public static void main(String[] args)

Reads an integer n and a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer in the pair represents some element; if the elements are in different sets, merge the two sets and print the pair to standard output.

Parameters:

args - the command-line arguments