Strongly Connected Components (Tarjan and Kosaraju)

This is an extension topic beyond most interviews; it pays off in hard OAs about directed graphs with cycles, where collapsing cycles into single vertices turns the problem into a DAG problem.

Intuition

In a directed graph, two vertices are strongly connected if each can reach the other. That relation splits the vertices into strongly connected components (SCCs): maximal groups where everybody reaches everybody. A DAG has only single-vertex SCCs; one big cycle is a single SCC.

The key structural fact: if you shrink every SCC into one vertex, the result (the condensation) is always a DAG. Any cycle among components would merge them into one. So "directed graph with cycles" questions often become "DAG" questions: topological order, DP over the condensation, counting sources and sinks.

Two linear-time algorithms:

• Tarjan. One DFS. Each vertex gets a discovery index dfn and a value low = the smallest index reachable from its DFS subtree using edges into vertices that are still on the stack (not yet assigned to a component). A vertex with low == dfn is the first-visited vertex (root) of its SCC; everything above it on the stack belongs to the same component.
• Kosaraju. Two DFS passes. First record finishing order on the original graph. Then, on the reversed graph, start from the vertex that finished last; whatever it reaches is exactly its SCC. Repeat in decreasing finish order.

When to use it in interviews / OAs

• "Groups of mutually reachable nodes", "cities that can all reach each other", "circular dependencies".
• "Minimum number of starting vertices so that everything is reachable": count SCCs with no incoming edge in the condensation.
• "Minimum edges to add so the graph becomes strongly connected": max(#sources, #sinks) of the condensation (0 if it is already one SCC).
• "Vertex reachable from all others" (popular node): exactly one sink SCC must exist.
• Longest path or maximum collected value when vertices may be revisited: DP on the condensation, where each SCC contributes its whole value.

Template

Both versions are iterative: recursive DFS in Python fails around a thousand levels deep.

Tarjan (iterative)

def tarjan_scc(n: int, adj: list[list[int]]) -> list[int]:
    # comp[v] = SCC id; ids come out in reverse topological order of the condensation
    dfn = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack: list[int] = []
    comp = [-1] * n
    timer = ncomp = 0
    for s in range(n):
        if dfn[s] != -1:
            continue
        dfn[s] = low[s] = timer
        timer += 1
        stack.append(s)
        on_stack[s] = True
        work = [(s, iter(adj[s]))]
        while work:
            u, it = work[-1]
            for v in it:
                if dfn[v] == -1:  # tree edge: descend into v
                    dfn[v] = low[v] = timer
                    timer += 1
                    stack.append(v)
                    on_stack[v] = True
                    work.append((v, iter(adj[v])))
                    break
                if on_stack[v]:  # edge into the still-open part of the DFS
                    low[u] = min(low[u], dfn[v])
            else:  # u is finished
                work.pop()
                if work:
                    p = work[-1][0]
                    low[p] = min(low[p], low[u])
                if low[u] == dfn[u]:  # u is the root of an SCC: pop it off
                    while True:
                        x = stack.pop()
                        on_stack[x] = False
                        comp[x] = ncomp
                        if x == u:
                            break
                    ncomp += 1
    return comp

Kosaraju (iterative)

def kosaraju_scc(n: int, adj: list[list[int]]) -> list[int]:
    # comp ids come out in topological order of the condensation
    order, seen = [], [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        work = [(s, iter(adj[s]))]
        while work:
            u, it = work[-1]
            for v in it:
                if not seen[v]:
                    seen[v] = True
                    work.append((v, iter(adj[v])))
                    break
            else:
                work.pop()
                order.append(u)  # finishing order
    radj: list[list[int]] = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    comp, c = [-1] * n, 0
    for s in reversed(order):  # latest finisher first
        if comp[s] != -1:
            continue
        comp[s] = c
        stack = [s]
        while stack:
            u = stack.pop()
            for v in radj[u]:
                if comp[v] == -1:
                    comp[v] = c
                    stack.append(v)
        c += 1
    return comp

Using the condensation

def condensation(n: int, adj: list[list[int]], comp: list[int]) -> list[set[int]]:
    dag: list[set[int]] = [set() for _ in range(max(comp) + 1)]
    for u in range(n):
        for v in adj[u]:
            if comp[u] != comp[v]:
                dag[comp[u]].add(comp[v])  # a set drops parallel component edges
    return dag


def min_edges_to_strongly_connect(n: int, adj: list[list[int]]) -> int:
    comp = tarjan_scc(n, adj)
    dag = condensation(n, adj, comp)
    k = len(dag)
    if k == 1:
        return 0
    has_in = [False] * k
    for a in range(k):
        for b in dag[a]:
            has_in[b] = True
    sources = sum(not x for x in has_in)
    sinks = sum(not dag[a] for a in range(k))
    return max(sources, sinks)

sources alone answers "minimum number of starting vertices to reach the whole graph".

Complexity

Tarjan and Kosaraju are both O(n + m) time. Tarjan uses one pass and O(n) extra memory; Kosaraju is easier to explain but builds the reversed graph (O(n + m) more memory). Building the condensation is O(n + m).

Common pitfalls

• Recursion depth. Use the iterator-stack DFS; a chain of 10^5 vertices crashes a recursive version in Python.
• Updating low through finished vertices. An edge into a vertex that already belongs to a completed SCC (not on the stack) must be ignored; using it merges unrelated components.
• Wrong order in Kosaraju. The second pass must run on the reversed graph, starting from the latest finishing time.
• Mixing up id orders. Tarjan's ids are reverse topological; Kosaraju's are topological. Check before running a DP over the ids.
• The single-SCC case. Adding zero edges is enough when everything is already strongly connected; the max(sources, sinks) formula would say 1.
• Undirected graphs. SCCs are a directed notion; for undirected graphs you want connected components, or bridges and articulation points for "critical" questions.

Interview variations

• Minimum vertices to reach all nodes. For a DAG it is the in-degree-0 vertices; in general it is one vertex per source SCC.
• Popular vertex. If the condensation has exactly one sink, every vertex in it is reachable from everybody; otherwise no vertex is.
• Maximum collected value on a walk. Sum values inside each SCC, then longest path on the condensation DAG.
• Functional graphs (every vertex has exactly one outgoing edge, as in "maximum employees invited to a meeting"): each component is one cycle with trees hanging into it; peeling in-degree-0 vertices (Kahn) leaves exactly the cycle vertices, no full SCC machinery needed.
• 2-SAT. Boolean constraints of the form "a or b" reduce to SCCs on an implication graph; contest material, rarely asked.