SCC — Tarjan

Finds strongly connected components in a single DFS by tracking each node's discovery index and 'low-link' (the lowest index reachable through the subtree, including one back edge). A node where low equals its own index is an SCC root.

Category

Graphs

Time complexity

O(V + E)

Space complexity

O(V)

Pseudocode

DFS assigning index and low-link
on returning from a child: low = min(low, child.low)
on a back edge: low = min(low, target.index)
low == index ⇒ pop the stack as one SCC

Reference implementation

def strongconnect(u):
    index[u] = low[u] = counter++; stack.push(u)
    for v in adj[u]:
        if v not in index: strongconnect(v); low[u]=min(low[u],low[v])
        elif v in stack: low[u] = min(low[u], index[v])
    if low[u] == index[u]: pop_scc(u)

Open the interactive SCC — Tarjan visualisation →