The challenge
Find all strongly connected components of a directed graph in one DFS using discovery indices, low-link values, and a stack of vertices not yet assigned to a component.
The SCC stack is different from the recursion stack: a returned vertex can remain on it until its SCC root finishes.
Example
The SCCs are {E}, {C, D}, and {A, B, F}; their output order can differ from Kosaraju’s while the partition is identical.
Use the walkthrough below to inspect the input and each state change.
See Tarjan SCC, step by step
Follow the edges. Watch the state change.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| — | — | — | — | — | — |
Initialize discovery and low-link values.
Discovery is the DFS entry index. Low-link tracks the earliest active SCC candidate reachable through the DFS subtree.
discovery = [-1] * V; timer = 0SCC stack · top last
View input edges
A → B · B → F · F → A · B → C · C → D · D → C · D → E
Put it into code
A vertex with low[u] = index[u] is the root of a complete SCC.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
def tarjan_scc(adj):
n = len(adj)
index, low = [-1] * n, [-1] * n
stack, on_stack, components = [], [False] * n, []
timer = 0
def visit(u):
nonlocal timer
index[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True
for v in adj[u]:
if index[v] == -1:
visit(v)
low[u] = min(low[u], low[v])
elif on_stack[v]:
low[u] = min(low[u], index[v])
if low[u] == index[u]:
component = []
while True:
v = stack.pop()
on_stack[v] = False
component.append(v)
if v == u:
break
components.append(component)
for u in range(n):
if index[u] == -1:
visit(u)
return components#include <algorithm>
#include <functional>
#include <vector>
std::vector<std::vector<int>> tarjan_scc(
const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size()), timer = 0;
std::vector<int> index(n, -1), low(n, -1), stack;
std::vector<bool> on_stack(n, false);
std::vector<std::vector<int>> components;
std::function<void(int)> visit = [&](int u) {
index[u] = low[u] = timer++;
stack.push_back(u);
on_stack[u] = true;
for (int v : adj[u]) {
if (index[v] == -1) {
visit(v);
low[u] = std::min(low[u], low[v]);
} else if (on_stack[v]) low[u] = std::min(low[u], index[v]);
}
if (low[u] == index[u]) {
components.emplace_back();
int v;
do {
v = stack.back();
stack.pop_back();
on_stack[v] = false;
components.back().push_back(v);
} while (v != u);
}
};
for (int u = 0; u < n; ++u) if (index[u] == -1) visit(u);
return components;
}