UF

Class UF

Object
  UF

public class UF extends Object
extends Object

The UF class represents a union-find data data structure. It supports the union and find operations, along with a method for determining the number of disjoint sets.

This implementation uses weighted quick union. Creating a data structure with N objects takes linear time. Afterwards, all operations are logarithmic worst-case time.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary
`UF(int N)` Create an empty union find data structure with N isolated sets.

Method Summary
`boolean`	`connected(int p, int q)` Are objects p and q in the same set?
`int`	`count()` Return the number of disjoint sets.
`int`	`find(int p)` Return the id of component corresponding to object p.
`static void`	`main(String[] args)`
`void`	`union(int p, int q)` Replace sets containing p and q with their union.

Methods inherited from class Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

UF

public UF(int N)

Create an empty union find data structure with N isolated sets.

Method Detail

find

public int find(int p)

Return the id of component corresponding to object p.

count

public int count()

Return the number of disjoint sets.

connected

public boolean connected(int p,
                         int q)

Are objects p and q in the same set?

union

public void union(int p,
                  int q)

Replace sets containing p and q with their union.

main

public static void main(String[] args)