Data Structures -> DSU Rollback / Offline Dynamic Connectivity

Rollback-friendly union-find plus segment tree over time for offline add/remove connectivity timelines.

• Topic slug: data-structures/dsu-rollback
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 5
• Curated external problems: 2

Microtopics

• rollback-dsu
• snapshot
• rollback
• segment-tree-over-time
• edge-active-interval
• offline-dynamic-connectivity

Learning Sources

Source	Type
CP-Algorithms deleting from a data structure in O(T(n) log n)	Reference
USACO Guide offline deletion	Reference
CSES Dynamic Connectivity	Practice

Practice Sources

Source	Type
CSES Problem Set	Practice
Library Checker	Practice
Codeforces problemset	Practice

Repo Companion Material

Material	Type
DSU Rollback hot sheet	quick reference
Dynamic Connectivity note	anchor note
DSU rollback starter route	starter route
DSU tutorial	adjacent tutorial
Offline Tricks tutorial	compare point

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Connectivity	CSES	Hard	Advanced Techniques, Dynamic Connectivity	Offline; Data-Structure-Heavy; Timeline Modeling	DSU; Offline Reasoning; Half-Open Intervals	Rollback-DSU; Segment-Tree-Over-Time; Component-Count	The cleanest first exact benchmark for edge-lifetime intervals, rollback DSU, and component answers at every time state.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Graph Vertex Add Component Sum	Library Checker	Hard	Dynamic Connectivity	Offline; Verification; Data-Structure-Heavy	Rollback DSU; Component Metadata; Offline Dynamic Connectivity	Rollback-DSU; Segment-Tree-Over-Time; Component Metadata	A strong next-step verifier once rollback connectivity itself is trusted and component-value aggregation becomes the new difficulty.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
DYNAMICCONNECTIVITY	Dynamic Connectivity	primary	hard	dsu rollback; segment tree over time; offline dynamic connectivity	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py