union-find

A data structure that tracks which items belong to the same group, supporting "find the group of x" and "merge the groups of x and y".

In more detail

Each group is a tree whose root names the group, and find follows parent pointers to the root. With path compression and union by rank, both operations take amortised time that grows so slowly, with the inverse Ackermann function, that it is effectively constant. Kruskal's algorithm uses it to avoid creating cycles.

Related terms

Taught in

References