How would you implement Tarjan's algorithm for strongly connected components?

Question and scenario

The graph has n vertices and m directed edges. Vertices may have no outgoing edges, edges may repeat, and the graph is not guaranteed to be connected. A strongly connected component is a set in which every pair of vertices can reach each other. Return all components and explain how contracting them forms a directed acyclic graph.

What the interviewer is testing

• Can the candidate maintain DFS indices, low values, stack membership, and component IDs correctly?
• Can they distinguish tree edges, back edges, and edges to an already completed component when updating low?
• Do they cover disconnected graphs, self-loops, parallel edges, and recursion-depth risk?
• Can they state O(n+m) time and O(n) auxiliary space and test the invariants?

Clarifying questions to ask first

Confirm whether vertex IDs are contiguous, whether parallel edges are allowed, whether component members need sorting, and whether the runtime limits recursion depth. Clarify graph size, incremental-update needs, and whether only a same-component query is required. For a very deep graph, state the trade-off between recursion and an explicit stack.

A 30-second answer framework

Run one DFS and assign each vertex an increasing index and the smallest index reachable by a back edge, called low. Push and mark each vertex, then inspect neighbors: recurse on an unvisited neighbor and use its low; for a neighbor still on the stack, use its index. When low equals the vertex's own index, it is a component root; pop until that vertex. Each vertex and edge receives constant work, so the complexity is O(n+m).

Step-by-step deep dive

1. Initialize state. Keep an index, low, stack-membership flag, and component ID for each vertex. Start DFS from every unvisited vertex to cover disconnected input.
2. Process an unvisited neighbor. Recurse, then apply low[u] = min(low[u], low[v]). This records a path from the DFS subtree back to an earlier stack vertex.
3. Process a stack neighbor. If the neighbor is still on the stack, update low[u] with the neighbor's index. A vertex already popped into another component cannot participate in this backtrack.
4. Find a root and pop. When low[u] == index[u], u is the root. Pop and clear the membership flag until u is popped; those vertices form one strongly connected component.
5. Handle boundaries. A self-loop still yields a singleton component; parallel edges repeat the same minimum update; an isolated vertex becomes a singleton when it is pushed.
6. Validate and condense. Check that every vertex belongs to exactly one component and that edges between components form a DAG. Compare random small graphs with transitive closure or Kosaraju, then test complexity and stack depth on large graphs.

High-quality sample answer

I would maintain four arrays: an increasing index, a low back-link value, a stack-membership flag, and a component ID. On DFS entry, assign an index and push the vertex. For an unvisited neighbor, recurse and propagate its low value; for a neighbor still on the stack, propagate only that neighbor's index. Completed components never participate in the update.

When low[u] == index[u], u is a root, so pop until u and clear the flags. Start DFS from every unvisited vertex, so connectivity is not assumed. Every vertex is pushed and popped once and every edge is inspected once, giving O(n+m) time and O(n) auxiliary space. Tests cover self-loops, parallel edges, isolated vertices, long chains, multiple cycles, and disconnected graphs, plus component partitioning and the condensation DAG.

Common mistakes

• Updating from every visited neighbor's low value and accidentally backtracking across a completed component.
• Forgetting to clear stack membership after popping a component, so later edges treat old vertices as current ancestors.
• Starting DFS from one vertex and missing components in disconnected input.
• Interpreting low equal to the current index as “no edge” rather than “this vertex is the component root.”
• Exceeding the language stack limit without discussing an explicit stack, chunking, or runtime configuration.

Follow-up questions and responses

Why cannot a popped vertex update low?

It already belongs to a completed component and is no longer a backtrack ancestor on the current DFS path. Using its low value would cross component boundaries and destroy maximality.

How do you prove each component is popped once?

Each vertex is pushed once, and only a root can trigger popping. After popping, its stack flag is cleared and DFS never pushes it again, so each vertex belongs to exactly one component.

How do you choose Tarjan versus Kosaraju?

Tarjan uses one DFS and no transposed graph, which can reduce traversal and storage. Kosaraju uses two DFS passes and separates the stages clearly. Both are O(n+m); choose based on stack limits, readability, and the existing graph representation.