Graph AlgosGraph Algorithms

Tarjan's SCC

Find all strongly connected components in one DFS using discovery indices, low-link values and an explicit stack.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Stack (top → bottom)

empty

SCCs found

empty

1/29Tarjan runs one DFS. Each node gets a discovery index and a low-link; when they coincide the node roots an SCC, which is exactly what sits above it on the stack.

Current node (label = idx/low)On the stackIn a completed SCCDFS tree edgeBack edge lowering low

PseudocodeLearn Tarjan's SCC Algorithm →

1index = 0; stack = []
2def strongconnect(u):
3  idx[u] = low[u] = index; index += 1; stack.push(u); onStack[u] = true
4  for v in neighbors(u):
5    if v unvisited: strongconnect(v); low[u] = min(low[u], low[v])
6    elif onStack[v]: low[u] = min(low[u], idx[v])
7  if low[u] == idx[u]:
8    pop stack down to u → one SCC
9for u in nodes: if u unvisited: strongconnect(u)

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed