Trace Tarjan discovery and low-link values as one DFS stack emits maximal mutually reachable components.
Core idea
Tarjan's DFS gives each vertex a discovery index and the earliest stacked vertex reachable from its subtree. When those two values match, the vertex is the root of one complete component.
Read the visualization
Badges show discovery and low-link values, a ring marks vertices still on the Tarjan stack, and each pop assigns one permanent component color.
Discover this vertex, assign its discovery and low-link values, and push it on the stack.
6 dfn[u] = low[u] = idx++; // enter u: dfn=low=enter between enter
7 stk.push(u); onStk[u] =true; // enter stack
8for (constvof adj[u]) {
9if (dfn[v] ===-1) { // tree edge: v tree visit
10dfs(v);
11 low[u] = Math.min(low[u], low[v]); // subtree return tree
12 } elseif (onStk[v]) { // return edge: v tree stack middle
13 low[u] = Math.min(low[u], dfn[v]);
14 }
15 }
16if (low[u] === dfn[u]) { // u back SCC root
17constcomp:number[] = []; let w;
18do { w = stk.pop()!; onStk[w] =false; comp.push(w); }
19while (w !== u); // scc stack to u → one SCC
20 sccs.push(comp);
21 }
22 };
23for (let i =0; i < n; i++) if (dfn[i] ===-1) dfs(i);
24return sccs;
25}
node / edge6 point / 7 directed edge
current node0(dfn=0, low=0)
stack[0]
searched SCC0
1 / 17
Complexity and tradeoffs
Time: O(V+E). Space: O(V). Each vertex enters and leaves the Tarjan stack once, and every directed edge is inspected once.
Invariant: A stacked vertex belongs to an unfinished DFS component, and its low-link is the earliest discovery reachable without leaving the stack.
Where it fits
SCC condensation turns any directed graph into a DAG. It supports cycle grouping, dependency analysis, reachability preprocessing, and the satisfiability test used by 2-SAT.
