Class UnionFind¶

Class Documentation¶

class UnionFind¶

Implements the Union Find data structure to maintain disjoint sets efficiently. Uses path compression and union by rank to achieve running time linear in the number of elements times the inverse Ackermann function.

Public Functions

inline UnionFind(index max_element)¶

Create a new set representation with not more than max_element elements. Initially every element is in its own set.

Parameters:

max_element – maximum number of elements

void allToSingletons()¶

Assigns every element to a singleton set. Set id is equal to element id.

index find(index u)¶

Find the representative to element @u

Parameters:

u – element

Returns:

representative of set containing @u

void merge(index u, index v)¶

Merge the two sets contain @u and @v

Parameters:

• u – element u

• v – element v

Partition toPartition()¶

Convert the Union Find data structure to a Partition

Returns:

Partition equivalent to the union find data structure