Strongly Connected Components

In a directed graph, $u$ and $v$ are strongly connected if each can reach the other. The equivalence classes of this relation are the strongly connected components (SCCs).

Kosaraju — two passes, easiest to remember

vector<vector<int>> adj, radj;
vector<int> order, comp;
vector<bool> used;
 
void dfs1(int u) {
    used[u] = true;
    for (int v : adj[u]) if (!used[v]) dfs1(v);
    order.push_back(u);                       // push on exit
}
void dfs2(int u, int c) {
    comp[u] = c;
    for (int v : radj[u]) if (comp[v] == -1) dfs2(v, c);
}
 
int kosaraju(int n) {
    used.assign(n, false); order.clear(); comp.assign(n, -1);
    for (int i = 0; i < n; i++) if (!used[i]) dfs1(i);
    int c = 0;
    for (int i = n - 1; i >= 0; i--)
        if (comp[order[i]] == -1) dfs2(order[i], c++);
    return c;
}

Why it works: the first DFS orders vertices by decreasing finish time. Processing them in that order on the reverse graph means each DFS cannot escape its own SCC — it would have to enter a component that finishes later, which the ordering forbids.

Tarjan — one pass

See Tarjan’s Algorithm. Uses tin/low plus an explicit stack; a vertex with low[u] == tin[u] is an SCC root, and the SCC is everything above it on the stack.

Gabow — one pass, two stacks

See Gabow’s algorithm. Replaces the low array with a second stack; slightly shorter and marginally faster.

	Passes	Extra arrays	Needs $G^{T}$
Kosaraju	2	order, used	yes
Tarjan	1	tin, low, onStack	no
Gabow	1	tin, two stacks	no

All are $O (V + E)$ and all emit components in reverse topological order of the condensation — which is what makes the next section work.

The condensation

Contract each SCC to a single node. The result is always a DAG — see Condensation Graph. This is the standard move: it reduces any directed-graph reachability problem to a DAG problem, where topological DP applies.

vector<vector<int>> cadj(numComp);
for (int u = 0; u < n; u++)
    for (int v : adj[u])
        if (comp[u] != comp[v]) cadj[comp[u]].push_back(comp[v]);
// deduplicate if needed

What SCCs immediately give you

Problem	Solution
Is the whole graph strongly connected?	one SCC
2-SAT	$x$ is true iff `comp[x] > comp[¬x]` (Tarjan numbering)
Minimum vertices to add edges from, to reach everything	number of sources in the condensation
Minimum edges to make the graph strongly connected	$max (# sources, # sinks)$ , or 0 if already one SCC
Largest set of mutually reachable vertices	biggest SCC
Longest path in a directed graph with cycles	condense, then longest path on the DAG
Does a cycle exist?	some SCC has size $> 1$ , or a self-loop exists
Vertices reachable from every vertex	sinks of the condensation with total reachability

The “minimum edges to make strongly connected” formula is worth memorising: after condensation, count sources (in-degree 0) and sinks (out-degree 0); the answer is $max (s, t)$ when the condensation has more than one node.

Common pitfall

Do not use undirected connected components on a directed graph when the problem cares about direction. Undirected components on a digraph give weakly connected components — a strictly coarser and usually wrong partition.

See also: Tarjan · Condensation · 2-SAT

whoashish's cp notes

Directory