path compression

A union-find optimisation: after finding a root, point every node visited on the way directly at that root.

In more detail

Later finds on those nodes take one step instead of many. It changes only the shape of the internal trees, never which group an item belongs to, so results stay correct.

Related terms

Taught in

References