public class WeightedQuickUnionUF extends Object
WeightedQuickUnionUF
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 size (without path compression). The constructor takes Θ(n), 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.
For alternative implementations of the same API, see
UF
, QuickFindUF
, and QuickUnionUF
.
For additional documentation, see
Section 1.5 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description 

WeightedQuickUnionUF(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 WeightedQuickUnionUF(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 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
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