Union Find

Data structure for undirected graphs that supports:

• edge addition: connect two vertices
• connectivity detection: determine whether two vertices are in the same connected component

__init__

Arguments

• n: int: number of vertices

Complexities

• time: $O(n)$
• space: $O(n)$

root

Returns the representative of the connected component containing vertex k. Useful to assign connected components values such as potential.

Arguments

• k: int: vertex

Returns

• int: representative of the connected component containing vertex k

Complexities

• $\text{amortized } O(\alpha(n))$

unite

Add an edge spanning between vertices i and j.

Arguments

• i: int: vertex
• j: int: vertex

Returns

• bool: True if the edge was essentially added (i and j were not connected), False otherwise

Complexities

• $\text{amortized } O(\alpha(n))$

is_connected

Returns whether vertices i and j are connected.

Arguments

• i: int: vertex
• j: int: vertex

Returns

• bool: True if vertices i and j are connected, False otherwise

Complexities

• $\text{amortized } O(\alpha(n))$

size

Returns the size of the connected component containing vertex k.

Arguments

• k: int: vertex

Returns

• int: size of the connected component containing vertex k

Complexities

• $\text{amortized } O(\alpha(n))$

Code Test

Run

Standard Output

Standard Error