Condensation Graph

Contract every strongly connected component of a directed graph into a single vertex. The result — the condensation — is always a DAG.

Why it is always acyclic

If the condensation had a cycle $C_{1} \to C_{2} \to \dots \to C_{1}$ , then every vertex in those components could reach every other, so they would all be one SCC. Contradiction with maximality. ∎

Building it

int numComp = tarjanSCC(n);                    // fills comp[0..n)
vector<set<int>> tmp(numComp);
for (int u = 0; u < n; u++)
    for (int v : adj[u])
        if (comp[u] != comp[v]) tmp[comp[u]].insert(comp[v]);
 
vector<vector<int>> cadj(numComp);
vector<int> compSize(numComp, 0);
for (int u = 0; u < n; u++) compSize[comp[u]]++;
for (int c = 0; c < numComp; c++) cadj[c].assign(tmp[c].begin(), tmp[c].end());

Both Tarjan and Kosaraju number the components in reverse topological order, so you often do not even need to run a topological sort afterwards — just iterate the component ids in the right direction.

The pattern

Condense, then run a DAG algorithm.

This is one of the highest-leverage moves in directed-graph problems. Anything that is hard because of cycles becomes easy on the DAG:

Problem on a general digraph	After condensation
Longest path (NP-hard in general graphs)	linear DP on the DAG
Maximum vertices collectible along a walk	DAG DP weighted by component size
Reachability counting	DAG DP with bitsets, $O (V E /64)$
“Can every vertex reach every other?“	is the condensation a single node
Minimum starting vertices to cover everything	number of sources in the condensation
Minimum edges to make it strongly connected	$max (# sources, # sinks)$ , or $0$ if already one SCC
Vertices reachable from all others	the unique sink if it dominates, else none
2-SAT	comparison of component ids

The two classic formulas

Minimum sources to cover. Every source component must be entered from outside or started in, so the answer is the number of in-degree-0 components.

Minimum edges for strong connectivity. With $s$ sources and $t$ sinks in a condensation of $\geq 2$ nodes, the answer is $max (s, t)$ . Construction: pair each sink with a source it cannot already reach and add a back edge; then chain whatever is left over.

Worked example

“Given a directed graph, find the maximum sum of vertex weights over all walks.”

A walk may loop inside an SCC arbitrarily, so it collects the entire component. Condense, set each component’s weight to the sum of its vertices, and take the longest path on the DAG:

for (int c = numComp - 1; c >= 0; c--)          // reverse topological order
    for (int d : cadj[c])
        dp[c] = max(dp[c], dp[d]);
dp[c] += weight[c];

Watch out

Duplicate edges. Contracting can produce many parallel edges; deduplicate if the algorithm downstream is sensitive to edge count.
Self-loops. Edges inside a component disappear. If a self-loop matters (e.g. “can we stay here forever”), record it separately.
Component ordering direction. Tarjan numbers components in reverse topological order; Kosaraju’s second pass numbers them in topological order. Check which one your implementation produces before relying on it.

whoashish's cp notes

Directory