Disjoint Set Union (DSU)
Disjoint Set Union: find and union with path compression — almost O(1).
The problem: elements merge into groups, and we need fast answers to "are a and b in the same group?" and "merge the groups of a and b". Naively — slow; DSU (Disjoint Set Union) does both operations in almost O(1).
The idea: each group is a tree, the group's representative is the root. find(v) climbs to the root; union hangs one root under another.
Two heuristics make the structure lightning fast:
• path compression: on the way to the root, re-hang all visited vertices directly onto the root;
• union by rank: the smaller tree is hung under the larger one.
DSU. Enter: 5 5, then the queries: union 1 2 / union 3 4 / check 1 3 / union 2 3 / check 1 4
Run the example: after union 1 2 and union 3 4, vertices 1 and 3 are in different groups (NO); after union 2 3 — in the same one (YES).
The line parent[v] = find(parent[v]) is that very path compression: returning from the recursion, every visited vertex gets hung directly onto the root. With both heuristics the amortized complexity is the inverse Ackermann function — in practice indistinguishable from a constant.
Where DSU shines: counting connected components as edges are added, Kruskal's algorithm for the minimum spanning tree (level 4), "merge and query" problems.
Task: add group-size tracking to the DSU (a size array; on union, size[a] += size[b]) and answer the query "how many elements are in the group of x".
Mark the lesson as completed — Level 3 is done, graphs are ahead!