Tarjan's Algorithm — Strongly Connected Components in Linear Time [Google, Meta, Uber]

Algorithm Statement#

Given a directed graph with n vertices and m edges, find all Strongly Connected Components (SCCs) — maximal subsets of vertices such that every vertex in the subset can reach every other vertex in the subset. Use Tarjan's algorithm, which performs a single DFS and produces every SCC in O(V + E) time using discovery times, low-link values, and an auxiliary stack.

Constraints:

• 1 <= n <= 10^5
• 0 <= m <= 2 * 10^5
• The graph is directed and may contain self-loops or multiple edges.

Example:

Input:  n = 5, edges = [[1,0],[0,2],[2,1],[0,3],[3,4]]
Output: SCCs = [[0,1,2], [3], [4]]
Explanation:
  0 -> 2 -> 1 -> 0 forms a cycle, so 0,1,2 is one SCC.
  3 has no incoming cycle, so 3 is alone.
  4 has no outgoing edges, so 4 is alone.

Why This Problem Matters#

Strongly Connected Components are foundational in compiler optimization, social-network cluster analysis, web-graph crawling, and dependency cycle detection in build systems. When Google clusters web pages by mutual reachability or when a build tool detects circular dependencies, an SCC algorithm sits at the core. Interviewers at Google, Meta, and Uber love SCC problems because they test multiple skills at once: DFS mastery, recursion-stack reasoning, and the subtle bookkeeping of discovery times and low-link values.

Tarjan's algorithm is preferred in interviews over Kosaraju's two-pass variant because it does a single DFS. That single pass is more elegant, has tighter constants, and demonstrates deeper understanding of graph traversal invariants. Problems like LeetCode 1192 (Critical Connections, which uses the same low-link technique for bridges) and LeetCode 2127 (Maximum Employees to be Invited to a Meeting) reward candidates who recognise the SCC pattern.

Beyond the leetcode lens, SCCs reduce a directed graph to a directed acyclic graph (DAG) — the condensation graph. Many otherwise-hard problems on directed graphs become tractable once you compute the SCC condensation: 2-SAT solvability, longest path in directed graphs, deadlock detection, and reachability queries.

The Core Insight#

Tarjan's algorithm tracks two numbers per vertex during DFS:

• disc[u] (discovery time): when DFS first visited u.
• low[u] (low-link): the minimum discovery time reachable from u using the DFS subtree rooted at u plus at most one back edge.

A vertex u is the root of an SCC when disc[u] == low[u]. At that moment, every vertex still on the auxiliary stack between u and the top of the stack belongs to the same SCC as u. Pop them off until you pop u itself.

The auxiliary stack records vertices currently in the active DFS path that have not yet been assigned an SCC. A boolean onStack[u] answers in O(1) whether u is on this stack — crucial when relaxing low[u] via back edges and cross edges.

The relaxation rules during DFS from u:

1. For an unvisited neighbour v: recurse, then low[u] = min(low[u], low[v]).
2. For a visited neighbour v that is on the stack: low[u] = min(low[u], disc[v]). Use disc[v], not low[v], because cross edges to vertices in already-finished SCCs must be ignored.
3. For a visited neighbour v not on the stack: ignore. It belongs to an earlier finished SCC.

When DFS returns to u and low[u] == disc[u] still holds, no back edge took low[u] lower than u's own discovery time. Therefore everything in u's DFS subtree currently on the stack forms one SCC.

Visual Dry Run#

Edges: 0->1, 1->2, 2->0, 1->3, 3->4

DFS from 0:

Final SCCs: {0,1,2}, {3}, {4}.

Solution (Optimal)#

Python#

import sys
from collections import defaultdict
 
def tarjan_scc(n, edges):
    sys.setrecursionlimit(10**6)
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
 
    disc = [-1] * n      # discovery time of each vertex
    low = [0] * n        # low-link value
    on_stack = [False] * n
    stack = []           # active DFS stack of unfinished vertices
    sccs = []
    timer = [0]          # mutable counter for closures
 
    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True
 
        for v in adj[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                # back edge to ancestor still on stack
                low[u] = min(low[u], disc[v])
            # else: cross edge to finished SCC -- ignore
 
        # u is the root of an SCC
        if low[u] == disc[u]:
            component = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)
                if w == u:
                    break
            sccs.append(component)
 
    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs

JavaScript#

function tarjanSCC(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
 
    const disc = new Array(n).fill(-1);
    const low  = new Array(n).fill(0);
    const onStack = new Array(n).fill(false);
    const stack = [];
    const sccs = [];
    let timer = 0;
 
    function dfs(u) {
        disc[u] = low[u] = timer++;
        stack.push(u);
        onStack[u] = true;
 
        for (const v of adj[u]) {
            if (disc[v] === -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
 
        if (low[u] === disc[u]) {
            const component = [];
            let w;
            do {
                w = stack.pop();
                onStack[w] = false;
                component.push(w);
            } while (w !== u);
            sccs.push(component);
        }
    }
 
    for (let i = 0; i < n; i++) {
        if (disc[i] === -1) dfs(i);
    }
    return sccs;
}

Complexity: Time O(V + E) because each vertex and edge is processed once. Space O(V) for arrays plus O(V) recursion depth in the worst case.

Common Mistakes#

1. Using low[v] instead of disc[v] for back edges. This corrupts the SCC root detection — low[v] may already point to a deeper finished SCC, causing premature merging.
2. Forgetting the onStack check. Without it, you would also relax low[u] against vertices already assigned to other SCCs, again causing wrong merges.
3. Stack overflow on deep graphs. Recursive Tarjan's can overflow on chains of 100k vertices in Python or JavaScript. Use iterative DFS or raise the recursion limit explicitly.
4. Treating undirected graphs as directed input. The SCC concept is meaningful only for directed graphs. For undirected, every connected component is trivially "strongly connected."
5. Ignoring multi-component graphs. Always loop over every vertex and start a fresh DFS for each unvisited one.
6. Confusing low-link with discovery time when popping. The pop loop continues until w == u, never w == low[u]. Otherwise you would underpop or overpop.

Interview Tips#

• Open by mentioning that Tarjan's runs in linear time and beats Kosaraju's in cache locality due to its single DFS pass.
• Define low-link precisely. Many candidates fumble here. Say: "the smallest discovery time reachable from u through the current DFS subtree plus at most one back edge to a still-active vertex."
• Walk through the four edge cases when DFS sees neighbour v: tree edge, back edge to active ancestor, forward edge inside subtree, cross edge to finished SCC.
• Mention that the SCCs are produced in reverse topological order of the condensation graph. This is useful in 2-SAT, where you must process SCCs in topological order.
• For huge graphs, mention iterative DFS to avoid recursion limits.

Follow-up Questions#

1. How do you build the condensation DAG from SCCs? Map each vertex to its SCC id, then create an edge between SCC ids whenever the original edge crosses SCCs. Deduplicate.
2. 2-SAT in linear time? Build the implication graph, run Tarjan, and check that no variable shares an SCC with its negation. Assignment comes from reverse topological order of SCCs.
3. What is Kosaraju's algorithm and when is it simpler? Two DFS passes (one on the original, one on the reverse). Simpler to teach but uses 2x memory and 2x DFS time.
4. Detect cycles in directed graph? Any SCC of size greater than 1 is a cycle, and any self-loop is also a cycle.
5. LeetCode 1192 (Critical Connections): Same low-link technique applied to undirected graphs to find bridges instead of SCCs.

Key Takeaways#

• Tarjan's algorithm finds all strongly connected components in a directed graph in O(V + E) using a single DFS.
• The two key arrays are disc (discovery time) and low (lowest disc reachable through subtree plus one back edge).
• A vertex is an SCC root precisely when disc[u] == low[u]. At that moment, pop the auxiliary stack until you remove u itself.
• Always relax low[u] against disc[v] (not low[v]) for back edges to active ancestors.
• SCCs come out in reverse topological order of the condensation DAG — a property leveraged by 2-SAT solvers.
• Tarjan's mental model — discovery times, low-links, and an explicit stack — generalises to bridges and articulation points in undirected graphs.