Class QuickUnionUF
 Object

 edu.princeton.cs.algs4.QuickUnionUF

public class QuickUnionUF extends Object
TheQuickUnionUF
class represents a union–find data type (also known as the disjointsets 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
, andWeightedQuickUnionUF
. 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 Description QuickUnionUF(int n)
Initializes an empty unionfind data structure withn
elements0
throughn1
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
count()
Returns the number of sets.int
find(int p)
Returns the canonical element of the set containing elementp
.static void
main(String[] args)
Reads an integern
and a sequence of pairs of integers (between0
andn1
) 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 elementp
with the set containing elementq
.



Constructor Detail

QuickUnionUF
public QuickUnionUF(int n)
Initializes an empty unionfind data structure withn
elements0
throughn1
. Initially, each element is in its own set. Parameters:
n
 the number of elements Throws:
IllegalArgumentException
 ifn < 0


Method Detail

count
public int count()
Returns the number of sets. Returns:
 the number of sets (between
1
andn
)

find
public int find(int p)
Returns the canonical element of the set containing elementp
. Parameters:
p
 an element Returns:
 the canonical element of the set containing
p
 Throws:
IllegalArgumentException
 unless0 <= p < n

union
public void union(int p, int q)
Merges the set containing elementp
with the set containing elementq
. Parameters:
p
 one elementq
 the other element Throws:
IllegalArgumentException
 unless both0 <= p < n
and0 <= q < n

main
public static void main(String[] args)
Reads an integern
and a sequence of pairs of integers (between0
andn1
) 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 commandline arguments

