What is Tarjan's Algorithm?
Learn how Tarjan's algorithm finds SCCs in one DFS pass using low-link values, and how to explain it clearly in interviews.
Expected Interview Answer
Tarjan's algorithm finds all strongly connected components (SCCs) of a directed graph in a single O(V + E) DFS pass by tracking each vertex's discovery time and the lowest discovery time reachable from it, popping a component off an explicit stack whenever a vertex's low-link equals its own discovery index.
Every vertex gets a discovery index in DFS order and a low-link value initialized to that same index; as DFS explores, each vertex is pushed onto an auxiliary stack marking it as being on the current recursion path. When an edge leads to an already-visited vertex still on the stack, the current vertex's low-link is updated to the minimum of its own low-link and that neighbor's discovery index, propagating back-edge information up the call stack. After exploring all of a vertex's neighbors, if its low-link still equals its own discovery index, it is the root of an SCC, and every vertex is popped off the stack down to and including that root to form the component. Because it needs only one DFS pass and no graph transpose, Tarjan's algorithm is often preferred over Kosaraju's in practice despite both running in O(V + E) time.
- Single DFS pass, no graph transpose needed
- O(V + E) linear time complexity
- Produces SCCs in reverse topological order
- Lower constant-factor overhead than Kosaraju’s two-pass approach
AI Mentor Explanation
Tarjan's algorithm is like a single scouting tour that finds mutual-rivalry clusters of cricket teams without ever retracing its steps. As the scout visits each team for the first time, they note a visit number and keep a running "lowest reachable visit number" for that team, updating it whenever a rival still on the current tour path is reached. The scout keeps a stack of teams currently on the active tour path, and when a team's lowest-reachable number matches its own visit number, that team is the anchor of a rivalry cluster, so every team above it on the stack gets popped off as one group. This single-pass bookkeeping is what lets the scout find every mutual rivalry cluster in one continuous tour instead of touring the league twice.
Step-by-Step Explanation
Step 1
Assign discovery index and low-link
On first visit, set both the discovery index and low-link of a vertex to the current counter, then push it onto a stack.
Step 2
Explore edges and update low-link
For each neighbor still on the stack, update the current vertex’s low-link to the minimum of itself and the neighbor’s discovery index.
Step 3
Detect SCC root
After exploring all neighbors, if a vertex’s low-link equals its own discovery index, it is an SCC root.
Step 4
Pop the component
Pop vertices off the stack down to and including the root to form one strongly connected component.
What Interviewer Expects
- Explain discovery index vs low-link value and how low-link propagates via back edges
- State the single-pass O(V + E) time complexity, no transpose needed
- Describe when and how an SCC is popped off the stack
- Compare tradeoffs against Kosaraju's two-pass approach
Common Mistakes
- Forgetting to check whether a neighbor is still on the stack before updating low-link
- Confusing discovery index with low-link value
- Not popping the stack correctly, merging unrelated components
- Assuming a graph transpose is required, which is unnecessary for Tarjan’s
Best Answer (HR Friendly)
“Tarjan's algorithm finds tightly-connected clusters in a one-way graph in a single pass. As I explore, I track how early I discovered each node and the earliest-discovered node I can loop back to, and whenever those two match, I've found the boundary of one cluster and pop it off my stack.”
Code Example
def tarjan_scc(n, graph):
index_counter = [0]
stack = []
on_stack = [False] * n
indices = [-1] * n
lowlink = [0] * n
sccs = []
def strongconnect(v):
indices[v] = index_counter[0]
lowlink[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
on_stack[v] = True
for w in graph[v]:
if indices[w] == -1:
strongconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif on_stack[w]:
lowlink[v] = min(lowlink[v], indices[w])
if lowlink[v] == indices[v]:
component = []
while True:
w = stack.pop()
on_stack[w] = False
component.append(w)
if w == v:
break
sccs.append(component)
for v in range(n):
if indices[v] == -1:
strongconnect(v)
return sccsFollow-up Questions
- How does Tarjan's algorithm avoid needing a graph transpose, unlike Kosaraju's?
- What order are SCCs discovered in relative to the condensation DAG?
- How would you convert this recursive implementation to an iterative one for very deep graphs?
- How would you use Tarjan’s algorithm to find articulation points instead?
MCQ Practice
1. How many DFS passes does Tarjan's algorithm require?
Tarjan's algorithm finds all SCCs in a single DFS pass using discovery indices and low-link values.
2. When is a vertex identified as the root of an SCC?
A vertex is an SCC root exactly when its low-link cannot reach any earlier-discovered vertex, i.e. low-link equals its discovery index.
3. What auxiliary structure does Tarjan's algorithm maintain during DFS?
It maintains an explicit stack tracking which vertices are on the current recursion path, used to pop off completed SCCs.
Flash Cards
What does Tarjan's algorithm compute, and in how many DFS passes? — All strongly connected components, in a single DFS pass.
What is a low-link value? — The lowest discovery index reachable from a vertex via its DFS subtree and back edges.
When is an SCC popped off the stack? — When a vertex’s low-link equals its own discovery index, marking it the SCC root.
How does Tarjan's differ structurally from Kosaraju's? — Tarjan’s needs only one DFS pass and no graph transpose; Kosaraju’s needs two passes and a transpose.