| UF Class |
The UF class represents a Union-Find data type (also known as the Disjoint-sets 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.
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 .
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class UF
The UF type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | UF |
Initializes an empty union-Find data structure with N sites
0 through N-1. Each site is initially in its own
component. |
Properties
Methods| Name | Description | |
|---|---|---|
| Connected |
Returns true if the the two sites are in the same component. |
| Find |
Returns the component identifier for the component containing site p. |
 | MainTest |
Reads in a 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 site;
if the sites are in different components, merge the two components
and print the pair to standard output. |
| Union |
Merges the component containing site p with the
the component containing site q. |
RemarksThis class is a C# port from the original Java class UF implementation by Robert Sedgewick and Kevin Wayne.
See Also