public class QuickFindUF extends Object
QuickFindUF
class represents a union–find data type
(also known as the disjoint-sets 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 union-find data structure with
n elements 0 through n-1 . |
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 n-1 ) 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 n-1
.
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 n-1
) 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 command-line arguments