Suppose you compute the condensation of a digraph and find that SCC node A has an edge to SCC node B, and SCC node B has an edge back to SCC node A. What must be true?
AThe original digraph is disconnected
BA and B were incorrectly identified as separate SCCs — they should be a single SCC
CThe condensation contains a valid cycle, which is normal for some digraphs
DEvery vertex in A can reach every vertex in B, but not vice versa
If SCC A can reach SCC B and B can reach A, then every vertex in A can reach every vertex in B and vice versa — meaning they form a single strongly connected component, not two separate ones. This contradicts the assumption that A and B are distinct SCCs. This is exactly why the condensation is always a DAG: any cycle between SCC nodes would imply those nodes should have been merged into a single SCC.
Question 2 Multiple Choice
Why is the condensation (metagraph) particularly useful for algorithmic problems on complex digraphs?
AIt reduces the number of edges in the graph to O(n)
BIt converts the digraph into a DAG, which supports topological ordering and dynamic programming
CIt eliminates all vertices with in-degree zero, simplifying the structure
DIt ensures all paths in the original graph are preserved without modification
The condensation is a DAG, and DAGs are significantly easier to work with than general digraphs: they have topological orderings, no circular dependencies, and support efficient dynamic programming. The condensation 'factors out' cyclic complexity — you analyze inter-SCC structure using the DAG, then separately analyze within-SCC structure. This two-level decomposition is the algorithmic payoff.
Question 3 True / False
The condensation of a directed acyclic graph (DAG) has fewer vertices than the original DAG.
TTrue
FFalse
Answer: False
False. In a DAG, every vertex is its own strongly connected component (since no cycles exist, no vertex can reach another and return). The condensation collapses each SCC to a single node, so a DAG with n vertices produces a condensation with n nodes — the same count. The condensation of a DAG is the DAG itself.
Question 4 True / False
Every directed graph, regardless of how complex or cyclic, has a unique condensation that is a DAG.
TTrue
FFalse
Answer: True
True. The SCCs of a directed graph are uniquely determined (every vertex belongs to exactly one SCC), so the condensation is unique. And the condensation must be a DAG: any cycle in the condensation would imply a cycle of reachability among distinct SCCs, forcing them to merge into a single SCC — a contradiction.
Question 5 Short Answer
Why is the condensation of any digraph guaranteed to be a DAG? Explain the reasoning.
Think about your answer, then reveal below.
Model answer: If the condensation had a cycle — say SCC A could reach SCC B and B could reach A — then every vertex in A could reach every vertex in B and vice versa, satisfying the definition of a single strongly connected component. This contradicts the assumption that A and B are separate SCCs. Therefore no cycle can exist in the condensation, making it a DAG.
The argument is a proof by contradiction: assume the condensation has a cycle and derive that the original SCC decomposition was incorrect. The uniqueness and acyclicity of the condensation follow from the maximality requirement in the definition of SCCs — they cannot be extended further without losing strong connectivity.