public class QuickFindUF extends Object
QuickFindUF
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 quick find.
Initializing a data structure with n sites takes linear time.
Afterwards, the find, connected, and count
operations take constant time but the union operation
takes linear time.
For alternate 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 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 sequence of pairs of integers (between 0 and n1) from standard input,
where each integer 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 QuickFindUF(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 count()
1
and n
)public int find(int p)
p
.p
 the integer representing one sitep
IllegalArgumentException
 unless 0 <= p < 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)
args
 the commandline arguments