Visualize Disjoint Set Union (DSU) operations step by step. Watch Path Compression flatten trees and Union by Rank keep them shallow, for near-O(1) amortized time.
Disjoint Set Union (DSU), also called Union-Find, is a data structure that tracks a set of elements partitioned into disjoint subsets. Two key operations run in near-O(1) amortized time thanks to Path Compression and Union by Rank.
Find(x) returns the root representative of x's component. Path Compression flattens the tree: every node on the path from x to root is directly attached to the root, making future finds O(1).
Union(x, y) merges the components of x and y. Union by Rank always attaches the shorter tree under the taller one, keeping trees shallow. Rank only increases when two trees of equal rank merge.
Two nodes are in the same component if and only if they share the same root. Call Find(x) and Find(y). If they return the same value, the nodes are connected.
With both optimizations, operations run in O(α(N)), which is effectively O(1) for any practical N. α is the inverse Ackermann function, which grows so slowly it never exceeds 4 for any real-world input.
Try Union, Find, and Connected on the 7 nodes. Operations are additive, so they build on each other. Notice how Path Compression flattens the tree on every Find.