Applications: Kruskal MST, Dynamic Connectivity, Equivalence Classes
What This Concept Is
DSU answers incremental undirected connectivity: edges can be added, but arbitrary deletion is outside the ordinary contract. It stores a partition, not the original graph. Kruskal uses that partition to detect whether a candidate edge would join two already-connected chosen components.
Why It Matters Here
A forest of DSU parent pointers need not be a subgraph of the selected MST. Conflating representation links with chosen edges produces invalid path witnesses and wrong deletion logic.
Concrete Examples
Kruskal. Sort physical edge records by weight. Keep an edge exactly when its endpoints are in different chosen components, then union them. Separately store that edge's original ID. The DSU partition matches connectivity of the chosen forest, but its parent pointers may connect vertices that never had a direct input edge. The spanning-forest cost includes O(V) initialization, O(E log(E+1)) sorting and aggregate union/find work.
Deletion counterexample. Insert edges 0-1 and 1-2; all three vertices become one class. Delete edge 1-2 from the graph. Ordinary DSU retains the merged class and cannot infer which vertices must separate. Cutting a DSU parent pointer is not equivalent to deleting the input edge, particularly after compression.
Offline deletion-only events. If the full sequence is known, begin with the final graph and process deletions backward as insertions. Duplicate edge records need multiplicity tracking: an edge remains present until its last copy is removed. Mixed additions/deletions need a richer approach, such as edge-active intervals plus rollback DSU. Rollback commonly omits compression and logs size/root changes; that is a different time/history contract.
Common Confusion / Misconceptions
Undirected equivalence is not strongly connected components. A connected answer does not supply a shortest path or an MST edge list. Weighted/potential DSU also needs consistent offset updates and contradiction handling; adding a delta field without a derived invariant is insufficient.
How To Use It
State allowed event types first. Use explicit edge IDs for graph artifacts and an independent BFS oracle for connectivity. In a deletion extension, show a failing ordinary-DSU example and choose a rebuild, reverse-time or rollback strategy with its own bounds. Do not silently preserve the insertion-only answer after a deletion.
Check Yourself
Why can a DSU parent edge be absent from the graph? What extra information does reversing deletions require? Why do duplicate edges matter?
Mini Drill or Application
Insert two copies of 0-1, then delete one. Feedback: graph connectivity stays true. Delete the second and it becomes false. A set-only event model that forgets multiplicity cannot distinguish these states.
Read This Only If Stuck
Skiena: Kruskal and disjoint sets; Competitive Programming: disjoint-set applications. Treat deletion handling as a separately specified extension.