Chapter 3 · Directed Graphs
Strongly Connected Components
Kosaraju and Tarjan in linear time, why the second pass needs the transpose, and the condensation as a working object.
A strongly connected component is a maximal set C ⊆ V such that every u,v ∈ C satisfy u ⇝ v and v ⇝ u. Maximality is what makes them a partition: if two vertex sets are mutually reachable into each other, they are one component.
Condensing each component into a single vertex gives the condensation GSCC — always a DAG (Orientations, In/Out-Degree, Strong vs Weak). The whole game is computing it in O(n+m).
#Kosaraju: two DFS passes
- DFS on G; record finish times.
- DFS on Gmathsf T (transpose), visiting vertices in decreasing finish time; each DFS tree is one SCC.
int n; vector<vector<int>> g, gt; vector<char> used(n); vector<int> order, comp(n, -1);
void dfs1(int u) { used[u] = 1; for (int v : g[u]) if (!used[v]) dfs1(v); order.push_back(u); }
void dfs2(int u, int c) { comp[u] = c; for (int v : gt[u]) if (comp[v] == -1) dfs2(v, c); }
void scc() {
for (int i = 0; i < n; i++) if (!used[i]) dfs1(i); // pass 1 on G
reverse(order.begin(), order.end());
for (int u : order) if (comp[u] == -1) dfs2(u, nxt_comp++); // pass 2 on G^T
}Ordering by decreasing finish time visits the SCCs in a topological order of the condensation — sources first. Hence in Gmathsf T the first unvisited DFS from a source component S cannot reach any other unvisited component, so it collects exactly S.
Take two distinct components A, B with an edge A → B in the condensation. No path B ⇝ A exists (else they'd be one component). Claim: finish(A) > finish(B), where finish(X) is the maximum finish time over X. Case 1 — DFS enters A first: it then reaches all of A and everything A reaches, including B; so B finishes inside A's window, strictly earlier than A's exit. Case 2 — DFS enters B first: B's whole search finishes without reaching A (no path B ⇝ A), so B finishes before A even starts. In the condensation, therefore, decreasing-finish order is a valid topological order. In Gmathsf T every inter-component edge points backwards along that order, so a search starting at a source of Gmathsf T (= source component of G in topological order) has its out-edges already assigned. ∎
#Tarjan: one pass, no transpose
Maintain a stack of "still open" vertices plus low[u] = smallest tin reachable from u's DFS subtree through open vertices. When low[u] = tin[u], pop the stack down to u: that is an SCC.
int timer = 0, ncomp = 0;
vector<int> tin(n, -1), low(n), st, comp(n, -1);
vector<char> on_st(n);
void dfs(int u) {
tin[u] = low[u] = timer++;
st.push_back(u); on_st[u] = 1;
for (int v : g[u]) {
if (tin[v] == -1) { dfs(v); low[u] = min(low[u], low[v]); }
else if (on_st[v]) low[u] = min(low[u], tin[v]); // tin, not low — the classic mistake
}
if (low[u] == tin[u]) {
while (true) { int x = st.back(); st.pop_back(); on_st[x] = 0; comp[x] = ncomp;
if (x == u) break; }
ncomp++;
}
}| Kosaraju | Tarjan | |
|---|---|---|
| passes | 2 | 1 |
| extra memory | the transpose Gmathsf T | stack + on_st |
| code you can re-derive under stress | yes — the proof is a case split | needs the low-link invariant |
| gives components in topological order | yes (naturally, reversed) | yes, in reverse topological order |
| iterative-friendly | very | moderately |
If you also need bridges/articulation points (Connectivity, Bridges, Articulation Points) you already have low-link machinery — use Tarjan. If you need the transpose anyway (e.g. for reachability or "mother vertex" arguments) Kosaraju's second DFS gives it for free.
#Using the condensation
Once you have comp[], rebuild a DAG on component indices and run any DAG algorithm on it:
set<pair<int,int>> dag_edges;
for (auto [u, v] : edges)
if (comp[u] != comp[v]) dag_edges.insert({comp[u], comp[v]});
// then: longest path, number of sources/sinks, DP over components, etc.Three classic one-liners after condensing
- Mother vertex: a vertex reaching all others exists ⇔ the condensation has exactly one source; test that source's reachability with one DFS.
- Minimum edges to make strongly connected (no parallel edges allowed): max(#sources, #sinks) of the condensation (1 if it is a single vertex) — pair sources to sinks greedily.
- "Assign a value to each vertex so all cycles agree": one value per component; the DAG then carries the constraints.
Two passes with the finish stack and growing component sets visible; switch to Gᵀ to watch pass 2 run on the transpose.