Class UF
 Object

 edu.princeton.cs.algs4.UF

public class UF extends Object
TheUF
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 weighted quick union by rank with path compression by halving. The constructor takes Θ(n) time, where n is the number of elements. The union and find operations take Θ(log n) time in the worst case. The count operation takes Θ(1) time. Moreover, starting from an empty data structure with n sites, any intermixed sequence of m union and find operations takes O(m α(n)) time, where α(n) is the inverse of Ackermann's function.
For alternative implementations of the same API, see
QuickUnionUF
,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 UF(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

UF
public UF(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

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

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

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

