edu.princeton.cs.algs4

## Class QuickUnionUF

• Object
• edu.princeton.cs.algs4.QuickUnionUF

• ```public class QuickUnionUF
extends Object```
The `QuickUnionUF` 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 union. The constructor takes Θ(n) time, where n is the number of sites. The union and find operations take Θ(n) time in the worst case. The count operation takes Θ(1) time.

For alternative implementations of the same API, see `UF`, `QuickFindUF`, 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
`QuickUnionUF(int n)`
Initializes an empty union-find data structure with `n` elements `0` through `n-1`.
• ### Method Summary

All Methods
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 the set containing element `q`.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### QuickUnionUF

`public QuickUnionUF(int n)`
Initializes an empty union-find data structure with `n` elements `0` through `n-1`. Initially, each elements 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 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