// Computes strongly connected components (SCCs).
// Input: directed graph G = (V, E).
// Output: integer array "component" with indices {0,…,|V|-1},
// satisfying component[u] = component[v] iff u and v
// belong to the same SCC.
scc((V, E)):
visited ← new array with indices {0,…,|V|-1} and
all elements equal to false
component ← new array with indices {0,…,|V|-1}
s ← empty stack containing node indices
// First depth-first search (DFS).
for v ∈ {0,…,|V|-1} do
if not visited[v] then
dfs₁(v)
// Reset the visited array.
for v ∈ {0,…,|V|-1} do
visited[v] ← false
// Second DFS.
n ← 0 // Component labels (0 for first component,
// 1 for second…).
while s non-empty do
v ← s.pop()
if not visited[v] then
dfs₂(v)
n ← n + 1
return component
// Subroutine for first DFS.
// Input: the starting node index v.
// Uses: E, visited and s.
dfs₁(v):
visited[v] ← true
// Note that the edges are followed in
// the reverse direction.
for w ∈ {w | (w, v) ∈ E} do
if not visited[w] then
dfs₁(w)
// Postorder insertion into stack.
s.push(v)
// Subroutine for second DFS.
// Input: the starting node index v.
// Uses: E, visited, component and n.
dfs₂(v):
visited[v] ← true
component[v] ← n
for w ∈ {w | (v, w) ∈ E} do
if not visited[w] then
dfs₂(w)
// Note: This code could have been more modular.