← All Tools

Tarjan's Strongly Connected Components Visualizer

Tarjan's SCC algorithm finds every maximal set of mutually reachable vertices in a directed graph in a single depth-first pass — O(|V| + |E|), no second graph, no reverse edges. Each vertex gets a DFS index and a low-link: the smallest index reachable from its subtree via any tree or back edge. When lowlink[v] == index[v], everything on the stack down to v is one SCC. Feed it a call graph to find mutually-recursive function clusters, feed it package imports to find dependency cycles, or feed it a currency exchange graph to find arbitrage loops.

Run stats

Vertices |V|0
Edges |E|0
DFS index counter0
Vertices on stack0
SCCs found0

DFS stack (bottom → top)

empty

SCCs (in pop order = reverse topological)

none yet

index / low-link table

Trace

tree edge · current vertex   back / on-stack   popped SCC

Why one DFS is enough

An SCC is a maximal set where every vertex reaches every other. When DFS enters a vertex v, everything reachable from v that has not been visited yet lives in v's DFS subtree. The low-link propagates upward the smallest DFS index that v's subtree can still reach via one back-edge or cross-in-same-SCC edge. If a subtree can escape backward to an earlier ancestor, all of it belongs with that ancestor's SCC; if it can't, then v is the entry point (or "root") of its own SCC, and every vertex on the stack above v is inside it — because they were pushed after v and none escaped. Popping the stack down to v gives the component in one clean sweep. The output arrives in reverse topological order of the condensation (each SCC seen as one super-node), which is exactly what a scheduler needs.