CustomCC0-1.0#ct-p6-052500
Dynamic SCC Longest Condensation Path
Summary
- •Phase 6 / combined-techniques
- •Reasoning-first competitive programming drill
Problem Description
Given directed graph and offline edge additions, report longest path length in SCC condensation after each step.
How to read this problem in plain language:
- This is a Phase 6 reasoning drill focused on combined-techniques.
- Typical lenses to test first: scc, offline, dag-dp.
- Constraints reminder: n,m <= 2e5
Mini examples for mental simulation:
1) Boundary example: Condensation has one node; longest path is 0 edges.
2) Adversarial example: SCC step should preserve original DAG structure.
Lite-mode writing target:
- Write 1~2 observations that shrink the search space.
- Name one final algorithm and state target complexity explicitly.
- Validate with at least 2 edge cases and one hand simulation.
Constraints
- •n,m <= 2e5
Analysis
Key Insight
Need block decomposition / batched recomputation strategy.
sccofflinedag-dp