DSA FOUNDATION
Disjoint-set foundations: partitions, representatives, and ownership
Union-find maintains an undirected equivalence partition under joins. Representatives encode membership, not graph routes, names, or canonical output order.
Mechanism and state
Initialize one parent-self root and root size one for every declared vertex, including isolated vertices. Find follows parents and uses iterative path halving: rewrite a nonroot to its grandparent and jump there. Union finds both roots, returns without joining when equal, otherwise attaches the smaller tree under the larger. This implementation keeps the first root on equal sizes and decrements a component counter only for a successful join. For accounts, vertices are source records and exact shared emails supply star-shaped join evidence; group final roots only after every late bridge is processed.
Why the pattern works
At every point parent chains are acyclic and root membership equals connectivity under processed evidence. Joining two roots merges exactly two components; halving changes no membership. Root sizes equal current set cardinalities, while nonroot size slots are stale. Size-based linking means a vertex’s component at least doubles whenever its root is attached, bounding uncompressed depth logarithmically. Combined with path halving, a sequence has inverse-Ackermann amortized operation cost; this is a sequence guarantee, not constant worst-case work for each find.
Work through an example
With vertices 0..3, join (0,1) and (2,3), then (0,2). Parent 3 can still point to 2 while 2 points to 0. A later find(3) rewrites 3 to grandparent 0 without changing component count. A failed union within this set can still shorten paths. In the eight-vertex balanced walkthrough, one halving pass may leave a path longer than one edge. For a triangle edge stream, the final same-root insertion closes an earlier graph path; the DSU root links themselves are not that path.
Where the reasoning fails
Do not attach arbitrary nonroot endpoints, decrement on duplicate/self edges, read nonroot sizes as current, or assume the representative is the minimum label. A dense province matrix still costs quadratic time to read. Sparse positive labels incur allocation through the largest label unless coordinate-compressed. Equal account names do not identify one person; exact email evidence and a conflict policy do. Ordinary DSU supports joins but cannot split a component after deleting evidence, and ordinary path compression complicates rollback.
Reconstruct the reasoning
Trace parent arrays, root sizes and component count after every balanced union in DSA-112, then separate a find’s structural changes from a union’s membership change. Compare the static BFS and DSU representation costs for a matrix versus an edge list. Explain why a failed edge insertion identifies redundancy but does not promise one-edge repair in an arbitrary multicycle graph. Construct a late account bridge whose root is not its earliest source index, and recover the required canonical output order. Apply the same component test in the all-pairs Kruskal baseline of DSA-117: explain why an accepted edge cannot form a cycle, and compare its quadratic edge storage with dense Prim.