Skip to content

DSU Rollback Hot Sheet

Use this page when the problem is still fundamentally about connectivity, but deletions or undo now block plain DSU.

Do Not Use When

  • only additions exist, so plain DSU hot sheet already fits
  • the problem is truly online and future events are unknown
  • the real question is path aggregate, shortest path, or subtree structure
  • one monotone offline sweep already solves the problem without rollback

Choose By Signal

Core Invariants

  • ordinary path compression is not the default here because every change must be undoable exactly
  • each successful union records one reversible change on a stack
  • an edge active on [l, r) is assigned to O(log q) nodes of a segment tree over time
  • at DFS leaf t, the DSU represents exactly the graph after the first t events

Main Traps

  • getting the time model wrong: add at i means active from state i, remove at i means inactive at state i
  • forgetting that initial edges start at time 0
  • using ordinary path compression and then being unable to rollback cleanly
  • not taking one snapshot per DFS node before applying that node's batch

Exact Starters In This Repo

Reopen Paths