Union-find cannot split a merged set — how would you support un-merging identity records in a live service?

## Why there is no split Union-find is a one-way structure. A merge writes a single link — one root now points at another — and every later lookup and flattening step rewrites parent entries with no memory of which merge caused what. Given a tree, there is no way to recover the partition that existed before some particular merge, and no way to identify which elements arrived through the merge you want to retract. Splitting is not slow here; it is not defined. That matters the moment the domain admits retraction. An identity service merging customer records on shared phone numbers and emails will eventually merge two people who share an office phone. A support agent must be able to say *these are two people* and have the system agree. ## Option 1 — rollback with an undo log Record, for each merge, the two entries it modified (the losing root's parent link and the winning root's size), and push them on a stack. Undo pops the stack and restores them. The cost is that **path flattening must be turned off**. Flattening rewrites an unbounded number of parent entries during an ordinary lookup, so undoing a merge would mean undoing an unbounded, interleaved set of writes that happened after it. Without flattening, merging by size still bounds tree height at O(log n), so lookups become logarithmic instead of near-constant. That is usually an acceptable price. The real constraint is **ordering**: an undo stack only reverses the most recent merge. It fits an algorithm that speculatively merges, explores, and backtracks, or an offline batch that processes a time-ordered edge set. It does not fit a live service where an agent retracts a merge made three months and four million merges ago. ## Option 2 — treat the structure as a derived cache and rebuild This is the option most live services should take. The system of record is the **evidence**: the append-only log of links (record 41 and record 90210 share verified email X). The union-find is a derived index built from that log. Retracting a merge then means: mark the evidence link as retracted, take the component that link belonged to, and recompute connectivity over just that component's remaining links. Everything outside the component is untouched. The cost is proportional to the component's size and edge count, not to the whole dataset. The risk that decides whether this works is **giant components**. Identity graphs are prone to them: one shared office phone number linking hundreds of records, one placeholder email address linking thousands. Once a single blob contains a meaningful share of the dataset, every retraction inside it is an expensive rebuild, and the rebuilds arrive exactly when a human is waiting on the answer. So the rebuild strategy is not just an algorithm choice; it is a commitment to keep components small, which means operational work: alarm on maximum component size, alarm on merges driven by a single high-degree key, and hold merges above a threshold for review rather than applying them automatically. ## Option 3 — a fully dynamic connectivity structure Structures exist that support edge insertion **and** deletion with polylogarithmic amortized cost per update. They are genuine and well studied, and they are also substantially more code than a parent array, with subtle invariants and an implementation nobody on the team will have seen before. The honest principal framing: this is a real option whose cost is not asymptotic but organisational. A dozen lines of parent-array logic can be maintained by anyone on the rotation; a dynamic connectivity structure becomes one engineer's private territory and a hazard when that engineer changes teams. Adopt it when measurement shows retractions are frequent enough and components large enough that rebuilds miss their latency target — not before. ## How I would actually decide 1. **Measure the retraction rate.** If un-merges are rare (a handful a day), rebuild wins outright; the operation is human-initiated and a few hundred milliseconds is invisible. 2. **Measure the component-size distribution, especially the maximum.** This is the variable that turns rebuild from cheap to catastrophic, and it drifts upward silently as data grows. 3. **Check the ordering of retractions.** If they are strictly LIFO — a speculative or batch workload — rollback is simple and fast, and the lost flattening barely matters. 4. **Only then consider the dynamic structure**, and budget for the fact that its real cost is ownership rather than cycles. ## What changes at ten times the data Component sizes do not scale linearly with the data; they scale with the connectivity of the evidence, and adding data adds edges that can merge previously separate blobs. So the failure mode at 10x is not a uniformly slower rebuild — it is the sudden appearance of one component holding a large fraction of the records, at which point the rebuild strategy fails all at once rather than degrading gracefully. That is why the component-size alarm is not a nice-to-have: it is the early warning that the architectural choice is about to expire.