public class UF extends Object
UF
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 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
, and WeightedQuickUnionUF
.
For additional documentation, see
Section 1.5 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description 

UF(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
the set containing element q . 
public UF(int n)
n
elements 0
through n1
.
Initially, each elements is in its own set.n
 the number of elementsIllegalArgumentException
 if n < 0
public int find(int p)
p
.p
 an elementp
IllegalArgumentException
 unless 0 <= p < n
public int count()
1
and 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
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