Tarjan's Strongly Connected Components

A single-pass depth-first algorithm that finds all strongly connected components of a directed graph in linear time.

Strong connectivity

A strongly connected component (SCC) of a directed graph is a maximal set of vertices where every vertex can reach every other. Contracting each SCC to a point yields a directed acyclic condensation. Tarjan's algorithm identifies all SCCs in a single depth-first traversal, in O(V + E).

Discovery and low-link

Each vertex gets a discovery index in DFS order and a low-link value: the smallest index reachable through its DFS subtree and back edges. Vertices are pushed onto a stack as they are visited. When a vertex's low-link equals its own index, it is the root of an SCC, and the component is exactly the stack entries down to and including that vertex.

Core recursion

python

def strongconnect(v):
    idx[v] = low[v] = counter[0]; counter[0] += 1
    stack.append(v); on_stack[v] = True
    for w in adj[v]:
        if idx[w] is None:
            strongconnect(w)
            low[v] = min(low[v], low[w])
        elif on_stack[w]:
            low[v] = min(low[v], idx[w])
    if low[v] == idx[v]:
        comp = []
        while True:
            w = stack.pop(); on_stack[w] = False
            comp.append(w)
            if w == v: break
        components.append(comp)

Tarjan versus Kosaraju

Kosaraju's algorithm uses two passes (a DFS on the graph and a DFS on its transpose) and is easier to explain; Tarjan uses one pass and no transpose, so it touches each edge once and tends to be faster. Both are O(V + E).

Uses

• Detecting cycles and analyzing dependency graphs.
• Building the condensation for further DAG algorithms.
• Solving 2-SAT by SCCs of the implication graph.