sketch_union_find.nx

sketch_union_find.nx -- Disjoint Set Union (Union-Find) primitive. Foundational data structure for connectivity / clustering. Maintains a partition of {0, 1, ..., n-1} into disjoint sets. Operations: find(x): which set is x in? (returns representative element) union(x, y): merge x's set with y's set connected(x, y): same set? size_of(x): cardinality of x's set OPTIMIZATIONS: - Path compression: find(x) flattens the parent chain so subsequent finds are O(1) on the same nodes. - Union by size: smaller tree attaches under larger; keeps tree height O(log n). With both optimizations: nearly-O(1) amortized per operation (technically O(α(n)) inverse-Ackermann; practically constant). USE CASES: - Kruskal's MST (connectivity tracking) - online clustering (merge clusters as new edges arrive) - dynamic connectivity (undirected only) - compilation: equivalence classes for SSA, alias analysis - image processing: connected components LOSSLESS-LANGUAGE DISCIPLINE: Production tier, exact semantics. No envelope returned -- operations are deterministic with O(α(n)) guarantee.