Union-Find (Disjoint Sets) with Union by Rank and Path Compression

Kruskal's algorithm needs to answer, for every candidate edge, "are these two vertices already in the same connected component?" — the disjoint-set (or union-find) problem: maintain a partition of a universe into disjoint sets, supporting find (which set is $x$ in?) and union (merge two sets). This note builds the forest-of-trees representation and its two classical optimisations — union by rank and path compression — which together give a running time so close to $O(1)$ per operation that it is, for any conceivable practical input size, indistinguishable from constant. The precise bound, and its proof, is deferred to the derivation sub-note.