Tarjan's algorithm finds every strongly connected component in a directed graph with a single DFS pass. It does not need to reverse the graph or run a second traversal, which is what Kosaraju's algorithm requires.

The same core idea also gives us bridges, articulation points, and 2-edge-connected components. These show up in network reliability problems, compiler optimization (finding loops in control flow graphs), and graph interview questions.

This chapter walks through how Tarjan's algorithm works, traces it step by step on a sample graph, and then extends the core idea to find bridges and articulation points.

What Is Tarjan's Algorithm?

Tarjan's algorithm is a depth-first search based algorithm that finds all strongly connected components (SCCs) in a directed graph in O(V + E) time using a single pass.

A strongly connected component is a maximal group of vertices where every vertex can reach every other vertex through directed edges. "Maximal" means you cannot add any more vertices to the group without breaking this property.

Consider this directed graph:

There are two SCCs here: {A, B, C} and {D, E}. Within {A, B, C}, you can follow directed edges from any vertex to any other. Same for {D, E}. But you cannot get from D or E back to A, B, or C, so these two groups remain separate components.

Robert Tarjan published this algorithm in 1972. The key insight is that during a single DFS, you can gather enough information to identify all SCCs without needing a second pass.

Key Concepts

Tarjan's algorithm relies on two values tracked for every vertex during the DFS traversal.

Discovery Time (disc)

The discovery time of a vertex is the order in which DFS first visits it. The first vertex visited gets disc = 0, the second gets disc = 1, and so on. This timestamps when each vertex was discovered.

Low-Link Value (low)

The low-link value of a vertex u is the smallest discovery time reachable from u (or any descendant of u in the DFS tree) by traveling down any number of tree edges and then taking at most one non-tree edge to a vertex still on the SCC stack. That non-tree edge can be a back edge to an ancestor or a cross edge to a vertex in a sibling subtree, as long as the target is still on the stack (meaning it has not yet been assigned to a completed SCC).

Initially, low[u] = disc[u] for every vertex u. As the DFS explores neighbors, low[u] gets updated if a path back to an earlier vertex is found. The difference between the two values is what Tarjan's relies on: disc[u] never changes after a vertex is first visited, while low[u] can drop as the search discovers a route back to an ancestor. When low[u] stays equal to disc[u], no such route exists, and u is the entry point of its component.

The Root Condition

A vertex u is the root of a strongly connected component if disc[u] == low[u]. This means that u cannot reach any vertex discovered earlier than itself, which means u is the "entry point" of its SCC in the DFS tree.

When this condition is met, everything on the stack from u to the top forms one complete SCC.

In this diagram, vertex u has disc = 2 and low = 2, making it the root of the SCC. Vertices v and w both have low = 2 because they can reach u (discovered at time 2) through the back edge from w to u. All three vertices form one SCC.

How Tarjan's Works

Here is the algorithm in plain English:

Initialize: Set a global timer to 0. Create arrays disc[] and low[], initialized to -1 (unvisited). Create an empty stack and a boolean array onStack[].

Start DFS from any unvisited vertex u:

Set disc[u] = low[u] = timer++
Push u onto the stack and mark onStack[u] = true

For each neighbor v of u:

If v is unvisited, recurse on v. After the recursion returns, update low[u] = min(low[u], low[v]).
If v is already on the stack (meaning v is part of the current DFS path and not yet assigned to an SCC), update low[u] = min(low[u], disc[v]).

After processing all neighbors of u: If disc[u] == low[u], then u is the root of an SCC. Pop vertices from the stack until u is popped. All popped vertices form one SCC.

Repeat for any remaining unvisited vertices (the graph may not be connected).

The stack does the central work here. It holds all vertices in the current DFS path that have not yet been assigned to an SCC. When we find a root (disc == low), we know everything above it on the stack belongs to the same SCC.

Implementation

Here is the full implementation of Tarjan's algorithm for finding strongly connected components.

disc[i] == -1 is used to check if vertex i is unvisited. This replaces the need for a separate visited[] array.
onStack[] is separate from the visited check. A vertex can be visited (disc != -1) but not on the stack if it has already been assigned to a completed SCC.
The time complexity is O(V + E) since every vertex and edge is processed exactly once during the DFS.
The space complexity is O(V) for the disc, low, onStack arrays and the stack.

Step-by-Step Walkthrough

Let us trace Tarjan's algorithm on a directed graph with 8 vertices and 3 SCCs.

The three SCCs are: {0, 1, 2}, {3, 4, 5}, and {6, 7}. Let us see how the algorithm discovers them.

Step 1: Visit vertex 0

disc[0] = 0, low[0] = 0
Stack: [0]
Recurse to neighbor 1.

Step 2: Visit vertex 1

disc[1] = 1, low[1] = 1
Stack: [1, 0]
Recurse to neighbor 2.

Step 3: Visit vertex 2

disc[2] = 2, low[2] = 2
Stack: [2, 1, 0]
Neighbor 0: already visited and on stack. low[2] = min(2, disc[0]) = min(2, 0) = 0.
Recurse to neighbor 3.

Step 4: Visit vertex 3

disc[3] = 3, low[3] = 3
Stack: [3, 2, 1, 0]
Recurse to neighbor 4.

Step 5: Visit vertex 4

disc[4] = 4, low[4] = 4
Stack: [4, 3, 2, 1, 0]
Recurse to neighbor 5.

Step 6: Visit vertex 5

disc[5] = 5, low[5] = 5
Stack: [5, 4, 3, 2, 1, 0]
Neighbor 3: already visited and on stack. low[5] = min(5, disc[3]) = min(5, 3) = 3.
Recurse to neighbor 6.

Step 7: Visit vertex 6

disc[6] = 6, low[6] = 6
Stack: [6, 5, 4, 3, 2, 1, 0]
Recurse to neighbor 7.

Step 8: Visit vertex 7

disc[7] = 7, low[7] = 7
Stack: [7, 6, 5, 4, 3, 2, 1, 0]
Neighbor 6: already visited and on stack. low[7] = min(7, disc[6]) = min(7, 6) = 6.
All neighbors processed. disc[7] = 7, low[7] = 6. Not a root. Return.

Step 9: Back at vertex 6

low[6] = min(low[6], low[7]) = min(6, 6) = 6.
All neighbors processed. disc[6] = 6, low[6] = 6. Root found.
Pop stack until 6: pop 7, pop 6. SCC = {6, 7}.
Stack: [5, 4, 3, 2, 1, 0]

Step 10: Back at vertex 5

low[5] = min(low[5], low[6]) = min(3, 6) = 3. After returning from a tree-edge recursive call into v, low[u] is updated with low[v] whether or not v is still on the stack. The on-stack check applies only to visited-but-not-recursed neighbors (back edges and cross edges), not to tree-edge returns.
low[5] = 3.
All neighbors processed. disc[5] = 5, low[5] = 3. Not a root. Return.

Step 11: Back at vertex 4

low[4] = min(low[4], low[5]) = min(4, 3) = 3.
All neighbors processed. disc[4] = 4, low[4] = 3. Not a root. Return.

Step 12: Back at vertex 3

low[3] = min(low[3], low[4]) = min(3, 3) = 3.
All neighbors processed. disc[3] = 3, low[3] = 3. Root found.
Pop stack until 3: pop 5, pop 4, pop 3. SCC = {3, 4, 5}.
Stack: [2, 1, 0]

Step 13: Back at vertex 2

low[2] = min(low[2], low[3]). But 3 is no longer on stack, so we keep low[2] = 0 from the back edge to vertex 0.
All neighbors processed. disc[2] = 2, low[2] = 0. Not a root. Return.

Step 14: Back at vertex 1

low[1] = min(low[1], low[2]) = min(1, 0) = 0.
All neighbors processed. disc[1] = 1, low[1] = 0. Not a root. Return.

Step 15: Back at vertex 0

low[0] = min(low[0], low[1]) = min(0, 0) = 0.
All neighbors processed. disc[0] = 0, low[0] = 0. Root found.
Pop stack until 0: pop 2, pop 1, pop 0. SCC = {0, 1, 2}.
Stack: []

Final state:

Vertex	disc	low	SCC
0	0	0	{0, 1, 2}
1	1	0	{0, 1, 2}
2	2	0	{0, 1, 2}
3	3	3	{3, 4, 5}
4	4	3	{3, 4, 5}
5	5	3	{3, 4, 5}
6	6	6	{6, 7}
7	7	6	{6, 7}

Within each SCC, all vertices share the same low-link value, and that value equals the disc value of the SCC's root.

Finding Bridges

The same disc and low values from Tarjan's algorithm can be used to find bridges in an undirected graph. A bridge is an edge whose removal disconnects the graph (or increases the number of connected components).

An edge (u, v) is a bridge if low[v] > disc[u]. This condition means that vertex v has no way to reach u or any ancestor of u without using the edge (u, v). Removing that edge would therefore disconnect v's subtree from the rest of the graph.

In this graph, the edge (2, 3) is a bridge. Vertices {0, 1, 2} form a cycle, so removing any edge between them still keeps them connected. But the only way to reach vertex 3 from vertices {0, 1, 2} is through that single edge.

Here is the implementation for finding bridges:

Key differences from the SCC version:

This works on undirected graphs, so we skip the parent edge to avoid treating it as a back edge.
There is no stack. We do not need to track SCCs, only detect the bridge condition.
The bridge check happens after the recursive call: if low[v] > disc[u], edge (u, v) is a bridge.

Finding Articulation Points

An articulation point (or cut vertex) is a vertex whose removal disconnects the graph. The logic is similar to finding bridges but with a slightly different condition.

A vertex u is an articulation point if either:

u is the root of the DFS tree and has two or more children in the DFS tree. If the root has only one child, removing it does not disconnect anything because the entire graph is in that one subtree.

u is not the root and there exists a child v such that low[v] >= disc[u]. This means no vertex in v's subtree can reach an ancestor of u without going through u.

In this graph, vertex 1 is an articulation point. Remove it, and {0, 2} gets disconnected from {3, 4}.

Here is the implementation for finding articulation points:

Using a set for articulation points avoids duplicates, since a vertex might satisfy the condition for multiple children.

Tarjan's vs Kosaraju's

Both algorithms find strongly connected components in O(V + E) time, but they take different approaches.

Aspect	Tarjan's	Kosaraju's
Number of DFS passes	1	2
Needs graph reversal	No	Yes
Extra data structures	Stack + disc/low arrays	Stack + reversed graph
Space overhead	O(V)	O(V + E) for reversed graph
Conceptual complexity	Higher	Lower
Output order	Reverse topological order	Topological order
Handles undirected graphs	With modifications (bridges, APs)	Not directly

When to prefer Tarjan's:

When memory is tight (no need to store the reversed graph).
When you also need bridges or articulation points (same core idea).
When you want everything done in a single pass.

When to prefer Kosaraju's:

When you want a simpler implementation that is easier to write correctly.
When topological order of SCCs matters directly (Kosaraju gives this naturally).
When you are already comfortable with its two-pass structure.

Complexity Analysis

Time Complexity

Tarjan's algorithm runs in O(V + E) time. It performs a single depth-first search that visits each vertex once and examines each edge once, computing the discovery and low-link values during that traversal. The bridge-finding and articulation-point variants reuse the same single DFS, so they also run in O(V + E).

Space Complexity

The algorithm uses O(V) space. It stores the disc and low arrays, an on-stack boolean array, and the explicit stack, each holding at most V entries, plus the recursion stack, which can grow to O(V) in the worst case. Storing the graph as an adjacency list takes O(V + E).

Key Takeaways

Tarjan's algorithm finds all strongly connected components of a directed graph in a single DFS pass, so it avoids the graph reversal and second traversal that Kosaraju's algorithm needs.
Each vertex tracks a discovery time (disc), which is the order DFS first visits it and never changes, and a low-link value (low), which is the smallest discovery time reachable through tree edges plus at most one back or cross edge to a vertex still on the stack.
A vertex u is the root of an SCC when low[u] == disc[u], and at that moment every vertex popped from the stack down to u forms one complete component.
The algorithm runs in O(V + E) time because it processes each vertex and edge once, and it uses O(V) space for the disc, low, and onStack arrays plus the stack.
The same disc and low values extend to undirected graphs: an edge (u, v) is a bridge when low[v] > disc[u], and a non-root vertex u is an articulation point when a child v satisfies low[v] >= disc[u].
A DFS root vertex is an articulation point only when it has two or more children in the DFS tree, since a single child means the whole graph sits in one subtree.

Quiz

Tarjan's Algorithm Quiz

10 quizzes