DSA DSA In Depth
0%
From-Scratch Build

Rollback Disjoint-Set Union & Offline Dynamic Connectivity Engine

A Rollback Disjoint-Set Union (Union-Find with undo stack) paired with a segment tree over the query timeline to solve offline dynamic graph connectivity with edge insertions and deletions.

~55 min Advanced Lessons: Weighted DSU (Potentials/Parity) & Rollback DSU for Dynamic Connectivity Over Time, Weighted DSU (Potentials/Parity) & Rollback DSU for Dynamic Connectivity Over Time, Disjoint Set Union (Union-Find): Union by Rank + Path Compression & O(α(N)) Proof Intuition, Segment Trees over Monoids: Recursive vs Iterative (ZKW) Bottom-Up Implementation, Minimum Spanning Trees: Cut & Cycle Optimality Properties, Kruskal's, Prim's & Borůvka's, Dynamic (Sparse) & Persistent Segment Trees: K-th Smallest in Subarray in O(log N)
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Why Standard DSU Cannot Delete Edges—And How Rollback DSU Solves It

Standard Disjoint-Set Union with path compression destroys historical tree structure: an arbitrary number of descendants may have repointed directly to the root. However, if we keep union by size/rank without path compression:

  • Tree height is strictly bounded by $\lfloor \log_2 n \rfloor$, so find(x) takes $O(\log n)$ worst-case time.
  • Every union(u, v) modifies exactly one parent pointer and one size entry, which can be undone in $O(1)$ time by popping an undo stack!

Offline Dynamic Connectivity via Segment Tree Over Time

While arbitrary deletions cannot be undone out of LIFO order directly, any sequence of $Q$ edge insertions, arbitrary edge deletions, and connectivity queries can be transformed into strictly LIFO operations over a Segment Tree of Time $[0..Q-1]$:

  1. Every edge $e$ added at time $t_1$ and deleted at time $t_2$ is alive over the contiguous time interval $[t_1, t_2 - 1]$.
  2. Insert $[t_1, t_2 - 1]$ into the segment tree over $[0..Q-1]$, splitting into $O(\log Q)$ canonical intervals.
  3. Run a DFS over the segment tree:
    • Take snap = dsu.snapshot() and union all edges attached to the current segment-tree node.
    • Recurse to left and right children (or answer the query at leaf $t$).
    • Call dsu.rollback(snap) on exit—strictly LIFO!

Total time complexity: $O((n + Q \log Q) \log n)$.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Union-by-Size Without Path Compression

  • Core Mechanical Concept: Union-by-Size Without Path Compression
  • Target Module: index.js (Step1)
  • Engineering Specification: Implement find(x) and union(u, v) on RollbackDSU. Omit path compression so find runs in $O(\log n)$ worst-case time while every union mutates only a single pointer and size.
  • Verification Invariant: verifies Step 1: Union-by-Size Without Path Compression

Step 2: O(1) Per-Operation Undo Stack & Rollback

  • Core Mechanical Concept: O(1) Per-Operation Undo Stack & Rollback
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement snapshot() and rollback(targetSnapshot) by popping { child, parent, prevSize } entries and restoring parent[child] = child and sz[parent] = prevSize.
  • Verification Invariant: verifies Step 2: O(1) Per-Operation Undo Stack & Rollback

Step 3: Edge Lifetime Decomposition Over a Time Segment Tree

  • Core Mechanical Concept: Edge Lifetime Decomposition Over a Time Segment Tree
  • Target Module: index.js (Step3)
  • Engineering Specification: Pair each addEdge(u, v) with its matching removeEdge(u, v) (or $T-1$ if never removed) to form a lifespan interval $[t_{\text{start}}, t_{\text{end}}]$ and insert it into $O(\log T)$ nodes of a Segment Tree over $[0..T-1]$.
  • Verification Invariant: verifies Step 3: Edge Lifetime Decomposition Over a Time Segment Tree

Step 4: Divide-and-Conquer Timeline DFS

  • Core Mechanical Concept: Divide-and-Conquer Timeline DFS
  • Target Module: index.js (Step4)
  • Engineering Specification: Traverse the time segment tree with DFS: on entering a node, snapshot the DSU and union all edges stored at that node; at leaves, answer queries; on exiting, rollback to the snapshot.
  • Verification Invariant: verifies Step 4: Divide-and-Conquer Timeline DFS

Asymptotic & Memory Layout Guarantees

  • Category: Graph Algorithms
  • Difficulty: Advanced (~55 minutes)
  • Key Architectural Highlights:
    • Path-compression-free Union-by-Size DSU with O(log n) find and O(1) exact undo stack
    • Snapshot & rollback API restoring exact parent pointers, component sizes, and component count
    • Offline Dynamic Connectivity over a time-segment tree solving edge additions, deletions, and queries in O((n + Q log Q) log n)
  • Tags & Primitives: Rollback DSU, Offline Dynamic Connectivity, Segment Tree over Time, Union by Rank, Undo Stack

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.