A disjoint-set forest keeps a partition of items into components using one parent pointer per node. find(x) walks up to the root; union(a, b) attaches one root under the other. With union by rank plus path compression, the amortized cost per operation drops to O(α(n)) — the inverse Ackermann function, which is under 5 for every conceivable input. Every Kruskal MST, every connectivity check, every UnionFind-on-Leetcode uses this exact structure.
component root visited by find just-linked root
Union by rank hangs the shorter tree under the taller so the combined tree grows in height only when both had equal rank — worst-case height O(log n). Path compression re-points every node visited during a find directly at the root, so the second find on the same chain is O(1). Alone, each gives O(log n) amortized; together, they achieve O(α(n)), where α is Tarjan's inverse Ackermann — for n up to 265536, α(n) ≤ 4. Toggle the checkboxes above and re-run the same sequence: without union-by-rank you can build long degenerate chains, then a single find with compression turned on flattens the whole thing in one shot.