DSU / Union-Find
Set StructuresEasyInteract with disjoint sets using union-by-rank and trace element trees in real time.
Alt+Shift+U
Configuration Panel
Complexity Mappings
Time ComplexityO(α(N)) near-constant time
Space ComplexityO(N) parent & rank sizes
DSU Representative Forest
Conceptual Overview
Disjoint Set Union (DSU) / Union-Find maintains a partition of elements into disjoint sets, supporting merge (Union) and query (Find) operations in near-constant time.
Algorithm Mechanism
Each set is represented as a tree. Union merges two trees by pointing the root of one to another. Find traverses parents to locate the root representative.
Source: CP-Algorithms reference guide