Class UF

java.lang.Object

UF

public class UF
extends java.lang.Object

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 determinig whether two sites 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 is-connected-to relation must be an equivalence relation:

• Reflexive: p is connected to p.

• Symmetric: If p is connected to q, q is connected to p.

• Transitive: If p is connected to q and q is connected to r, then p is connected to r.

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.

• union(p, q) adds a connection between the two sites p and q. If p and q are in different components, then it replaces these two components with a new component that is the union of the two.

• find(p) returns the component identifier of the component containing p.

• connected(p, q) returns true if both p and q are in the same component, and false otherwise.

• count() returns the number of components.

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 Summary

Constructors

Constructor and Description
UF(int N) Initializes an empty union-find data structure with N isolated components 0 through N-1

Method Summary

Methods

Modifier and Type	Method and Description
boolean	connected(int p, int q) Are the two sites p and q in the same component?
int	count() Return the number of components.
int	find(int p) Return the component identifier for the component containing site p.
static void	main(java.lang.String[] args) 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.
void	union(int p, int q) Merge the component containing site p with the the component containing site q.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UF

public UF(int N)

Initializes an empty union-find data structure with N isolated components 0 through N-1

Parameters:

N - the number of sites

Throws:

java.lang.IllegalArgumentException - if N < 0

Method Detail

find

public int find(int p)

Return the component identifier for the component containing site p.

Parameters:

p - the integer representing one object

Returns:

the component identifier for the component containing site p

Throws:

java.lang.IndexOutOfBoundsException - unless 0 ≤ p < N

count

public int count()

Return the number of components.

Returns:

the number of components (between 1 and N)

connected

public boolean connected(int p,
                int q)

Are the two sites p and q in the same component?

Parameters:

p - the integer representing one site

q - the integer representing the other site

Returns:

true if the two sites p and q are in the same component; false otherwise

Throws:

java.lang.IndexOutOfBoundsException - unless both 0 ≤ p < N and 0 ≤ q < N

union

public void union(int p,
         int q)

Merge the component containing site p with the the component containing site q.

Parameters:

p - the integer representing one site

q - the integer representing the other site

Throws:

java.lang.IndexOutOfBoundsException - unless both 0 ≤ p < N and 0 ≤ q < N

main

public static void main(java.lang.String[] args)

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.