Skip to content

Glossary: Algorithms Beyond the Basics

Union-find

Also written: union find, disjoint set union, DSU

A structure, also called disjoint set union, that tracks which items are in the same group as links arrive, using `find` and `union`. Each call is nearly O(1) with path compression and union by size.

Where the book teaches it

Related terms

Path compressionUnion by sizeKruskal's algorithm