public class QuickFindUF extends Object
QuickFindUF
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:
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.
Constructor and Description 

QuickFindUF(int n)
Initializes an empty unionfind data structure with
n elements 0 through n1 . 
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 n1 ) 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 . 
public QuickFindUF(int n)
n
elements 0
through n1
.
Initially, each element is in its own set.n
 the number of elementsIllegalArgumentException
 if n < 0
public int count()
1
and n
)public int find(int p)
p
.p
 an elementp
IllegalArgumentException
 unless 0 <= p < n
@Deprecated public boolean connected(int p, int q)
find(int)
.p
 one elementq
 the other elementtrue
if p
and q
are in the same set;
false
otherwiseIllegalArgumentException
 unless
both 0 <= p < n
and 0 <= q < n
public void union(int p, int q)
p
with the set
containing element q
.p
 one elementq
 the other elementIllegalArgumentException
 unless
both 0 <= p < n
and 0 <= q < n
public static void main(String[] args)
n
and a sequence of pairs of integers
(between 0
and n1
) 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.args
 the commandline arguments