public class UF extends Object
UF
class represents a union–find data type
(also known as the disjointsets data type).
It supports the union and find operations,
along with a connected operation for determining whether
two sites are in the same component and a count operation that
returns the total number of components.
The union–find data type models connectivity among a set of n sites, named 0 through n–1. The isconnectedto relation must be an equivalence relation:
An equivalence relation partitions the sites into equivalence classes (or components). In this case, two sites are in the same component if and only if they are connected. Both sites and components are identified with integers between 0 and n–1. Initially, there are n components, with each site in its own component. The component identifier of a component (also known as the root, canonical element, leader, or set representative) is one of the sites in the component: two sites have the same component identifier if and only if they are in the same component.
The component identifier of a component can change only when the component itself changes during a call to union—it cannot change during a call to find, connected, or count.
This implementation uses weighted quick union by rank with path compression
by halving.
Initializing a data structure with n sites takes linear time.
Afterwards, the union, find, and connected
operations take logarithmic time (in the worst case) and the
count operation takes constant time.
Moreover, the amortized time per union, find,
and connected operation has inverse Ackermann complexity.
For alternate 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 union–find data structure with
n sites
0 through n1 . 
Modifier and Type  Method and Description 

boolean 
connected(int p,
int q)
Returns true if the the two sites are in the same component.

int 
count()
Returns the number of components.

int 
find(int p)
Returns the component identifier for the component containing site
p . 
static void 
main(String[] args)
Reads in a 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 site;
if the sites are in different components, merge the two components
and print the pair to standard output. 
void 
union(int p,
int q)
Merges the component containing site
p with the
the component containing site q . 
public UF(int n)
n
sites
0
through n1
. Each site is initially in its own
component.n
 the number of sitesIllegalArgumentException
 if n < 0
public int find(int p)
p
.p
 the integer representing one sitep
IllegalArgumentException
 unless 0 <= p < n
public int count()
1
and n
)public boolean connected(int p, int q)
p
 the integer representing one siteq
 the integer representing the other sitetrue
if the two sites p
and q
are in the same component;
false
otherwiseIllegalArgumentException
 unless
both 0 <= p < n
and 0 <= q < n
public void union(int p, int q)
p
with the
the component containing site q
.p
 the integer representing one siteq
 the integer representing the other siteIllegalArgumentException
 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 site;
if the sites are in different components, merge the two components
and print the pair to standard output.args
 the commandline arguments