Algorithms / Condensation Dag
Least You Need to Know: Condensation DAGs and Component-Level Ordering
If each SCC is contracted to one node, the resulting graph is a DAG. This condensation DAG captures the one-way flow between strongly connected regions and is often the right object for topological reasoning after SCC decomposition.
Least you need to know
- Each SCC becomes one meta-node in the condensation graph.
- Edges between SCCs represent original directed edges crossing components.
- The condensation graph is always acyclic.
- Topological ordering applies cleanly after SCC contraction.
- Many dependency arguments are easier at the component level than at the raw vertex level.
Key notation
- cond(G) — condensation graph of directed graph G
- meta-node — one strongly connected component viewed as a single node
- DAG — directed acyclic graph
Worked example
- Suppose SCC
Ahas an edge to SCCB, andBhas an edge to SCCC. - In the condensation graph, this becomes
A → B → C. - If a cycle among meta-nodes existed, then all those SCCs would actually be mutually reachable and should merge into one larger SCC.
- That contradiction is why the condensation graph must be acyclic.
Common mistakes
- Students sometimes draw duplicate parallel edges; the presence of an edge matters more than multiplicity for most reasoning.
- A cycle inside an SCC does not make the condensation graph cyclic.
- Meta-nodes correspond to SCCs, not arbitrary DFS trees.
How to recognize it
- You want to reason about SCC dependencies or topological order after compression.
- The problem asks what happens after contracting strongly connected regions.
- Cycles should disappear once mutually reachable blocks are merged.
Next recommended lesson
Continue through this topic with Least You Need to Know: Coordinate Compression, Order Preservation, and Dense Indexing.
Least You Need to Know: Coordinate Compression, Order Preservation, and Dense IndexingRelated lessons
Keep going with nearby lessons in the same topic.