Tarjan's SCC Finder

Pseudocode

One DFS, one stack, two numbers per vertex. The insight is that a strongly connected component has a unique root: the vertex in it discovered first.

strongconnect(u):
    disc[u] = low[u] = ++time
    stack.push(u); onStack[u] = true

    for each edge (u, v):
        if v is unvisited:
            strongconnect(v)
            low[u] = min(low[u], low[v])
        else if onStack[v]:
            low[u] = min(low[u], disc[v])
        // else: v is in a finished SCC, ignore it

    if low[u] == disc[u]:          // u is an SCC root
        pop the stack down to and including u
        that popped set is one SCC

The onStack test is what separates Tarjan from a naive low-link scheme. An edge into a vertex that is visited but already assigned to a finished component tells you nothing about your own component and must be skipped. Including it would merge two genuinely separate SCCs. Note also the asymmetry: a tree edge folds in low[v], a back edge folds in disc[v], and mixing those up is the other classic bug.

Worked example, step by step

Run Tarjan on a directed graph holding one three-cycle, one two-cycle, and one vertex that belongs to neither.

Example graph: Directed edges A to B, B to C, C to A, B to D, D to E, E to D, and C to F.

1. Descend A, B, C. disc and low start equal: A gets 1, B gets 2, C gets 3. All three are on the stack.
2. C to A is a back edge. A is visited and still on the stack, so low[C] = min(3, disc[A] = 1) = 1. Note it uses disc[A], not low[A].
3. C to F, and F pops alone. F gets disc 4 and has no outgoing edges, so low[F] stays 4. Since low[F] equals disc[F], F is an SCC root and pops by itself as the component {F}. A vertex on no cycle is always its own singleton SCC.
4. B to D to E, and E loops back. D gets disc 5, E gets disc 6. The edge E to D finds D on the stack, so low[E] = min(6, disc[D] = 5) = 5. E is not a root, since low[E] of 5 does not equal disc[E] of 6, so nothing pops yet.
5. D is a root. Back at D, low[D] = min(5, low[E] = 5) = 5, which equals disc[D]. D is an SCC root, so the stack pops E then D, giving the component {D, E}.
6. A is a root. Unwinding, low[B] = min(2, low[C] = 1, low[D] = 5) = 1 and low[A] = min(1, low[B] = 1) = 1, which equals disc[A]. The stack pops C, B, A, giving {A, B, C}.

Final low-links are A 1, B 1, C 1, F 4, D 5, E 5, and the components come out in the order {F}, then {D, E}, then {A, B, C}. Two things are worth noting. Components are emitted in reverse topological order of the condensation, which is why Tarjan is the usual first step for 2-SAT. And F, reachable from the cycle but with no way back, is correctly its own component rather than being absorbed into {A, B, C}.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

A single depth-first search visits each vertex once and examines each directed edge exactly once, giving O(V + E). Each vertex is pushed onto the stack once and popped once, so the stack operations total O(V) across the whole run. The extra state is the discovery time, the low-link and the on-stack flag per vertex, plus the recursion stack, all O(V). Tarjan does this in one pass, where Kosaraju needs two full traversals plus the construction of the transposed graph, which is why Tarjan is usually preferred in practice even though both are linear.

When to use Tarjan's SCC Algorithm, and when not to

All three linear SCC algorithms have the same asymptotic cost, so the choice is about constants, memory and how easy the code is to get right.

Common pitfalls

• Using low[v] instead of disc[v] on a back edge. For a tree edge you fold in low[v]; for a back edge to a vertex on the stack you fold in disc[v]. Using low[v] for back edges can pull in a value from a different component and merge SCCs that should stay separate. The two cases are genuinely different.
• Omitting the onStack check. An edge to a visited vertex that has already been popped into a finished SCC must be ignored entirely. Without the check, low-links leak across component boundaries and the output is wrong on any graph with cross edges.
• Forgetting to clear onStack when popping. Every vertex popped into a component must have its flag cleared. Leaving it set makes later back-edge tests fire against vertices that are no longer on the stack, silently corrupting subsequent components.
• Recursing on very large graphs. Tarjan is naturally recursive and the depth is the length of the longest path. On graphs with hundreds of thousands of vertices in a chain the call stack overflows, and an explicit-stack rewrite is required. This is fiddlier than for plain DFS because the low-link update must happen after each child returns.
• Assuming a component order that is not there. Tarjan emits components in reverse topological order of the condensation, not in any order related to vertex labels. If you need forward topological order, reverse the output.

Frequently asked questions

What is a strongly connected component?

A strongly connected component of a directed graph is a maximal set of vertices in which every vertex can reach every other by following directed edges. Maximal matters: you cannot add another vertex and keep the property. A vertex on no directed cycle forms a component by itself.

How does Tarjan's algorithm work?

It runs one depth-first search, assigning each vertex a discovery index and a low-link value, the smallest index reachable from its subtree using at most one back edge to a vertex still on the stack. Vertices are pushed on a stack as they are visited. When a vertex finishes with its low-link equal to its own index, it is the root of a component, and everything above it on the stack is popped as that component.

What is the difference between Tarjan's and Kosaraju's algorithm?

Both find strongly connected components in O(V + E). Tarjan uses a single DFS with low-link bookkeeping and a stack. Kosaraju uses two DFS passes, one on the original graph to get finish times and one on the transposed graph in decreasing finish order. Kosaraju is easier to explain; Tarjan is faster in practice since it avoids building the transpose and traverses only once.

What is the time complexity of Tarjan SCC?

O(V + E) time and O(V) space. Each vertex is visited once, each edge examined once, and each vertex is pushed and popped from the stack exactly once. This is optimal, since any algorithm must read the entire graph.

What are strongly connected components used for?

Condensing a directed graph into a DAG, which is the first step in solving 2-SAT. Also call-graph analysis and dead code elimination in compilers, deadlock detection, finding mutual dependencies in package managers and spreadsheets, and community structure in directed social networks.