Tarjan's SCC, in depth: low-links, the on-stack rule, an iterative implementation and what the condensation buys you

What a strongly connected component is

Write u ~ v when u can reach v and v can reach u. The relation is reflexive, symmetric and transitive, so it partitions the vertices into equivalence classes, and those classes are the SCCs. A vertex on no cycle is an SCC of size one. A self-loop does not change that; it only makes the single vertex cyclic, which matters if you are hunting cycles rather than components.

The condensation of a graph has one node per SCC and an edge from component X to component Y when some edge goes from X to Y. It is always acyclic: if X reached Y and Y reached X, they would be one component. That is where the usefulness comes from. Build tools sort the condensation to order work with each cycle treated as one unit, compilers analyse mutually recursive functions together, and deadlock detectors look for an SCC of size greater than one in a wait-for graph.

The traversal machinery here, discovery order and tree, back and cross edges, is covered in BFS and DFS, in depth. The only extra ideas Tarjan needs are a stack and a number per vertex called the low-link.

The idea: one DFS, a stack and low-links

Run a depth-first search and number the vertices in the order they are discovered; call that index[v]. Push each vertex onto a separate stack when it is discovered, and do not pop it when its DFS call returns. Vertices stay on that stack until their whole component is identified.

The low-link low[v] is the smallest index of any vertex that is still on the stack and that can be reached from v's DFS subtree by following tree edges down and then at most one non-tree edge. It is computed bottom-up. Start with low[v] = index[v]. For each edge v to w: if w is undiscovered, recurse into it and then take low[v] = min(low[v], low[w]). If w is discovered and still on the stack, take low[v] = min(low[v], index[w]). If w is discovered and off the stack, ignore the edge.

When v's DFS call finishes, compare the two numbers. If low[v] == index[v], nothing in v's subtree can reach anything on the stack below v, so v is the first-discovered vertex of its component, the root. Every vertex above v on the stack belongs to the same component. Pop them down to and including v and emit that set as an SCC.

Why the root test is correct

Two facts carry the proof. First, the first-discovered vertex r of a component reaches every other member, none of which has been visited yet, so the DFS explores the whole component inside r's subtree and the stack holds it above r.

Second, a vertex v with low[v] < index[v] can reach a vertex still on the stack that was discovered before v. That vertex is an ancestor of v, or it is in the same open component as an ancestor, and either way it reaches v through the tree. So v and that earlier vertex are in the same component, and v is not a root. Conversely, if low[v] == index[v], nothing in the subtree escapes to an earlier open vertex, so the component cannot extend below v on the stack. The vertices above v are exactly its component, because anything from another component in the subtree was already popped when its own root finished.

This is why the off-stack rule matters. A popped vertex belongs to a finished component that cannot reach back to v, or it would have included v. An edge into it is not evidence of a cycle, and using its index would wrongly merge components.

Two implementations

The recursive version is the clearest statement of the algorithm and is fine for small graphs:

def tarjan_recursive(graph):
    """graph: dict vertex -> list of successors. Every vertex must be a key."""
    index, low, on_stack, stack, sccs = {}, {}, set(), [], []
    counter = 0

    def strongconnect(v):
        nonlocal counter
        index[v] = low[v] = counter
        counter += 1
        stack.append(v)
        on_stack.add(v)
        for w in graph[v]:
            if w not in index:                 # tree edge: recurse, then pull up w's low-link
                strongconnect(w)
                low[v] = min(low[v], low[w])
            elif w in on_stack:                # edge into the current DFS path's open SCCs
                low[v] = min(low[v], index[w])
            # else: w belongs to a finished SCC -- ignore it
        if low[v] == index[v]:                 # v is the root of an SCC: pop it
            comp = []
            while True:
                w = stack.pop()
                on_stack.discard(w)
                comp.append(w)
                if w == v:
                    break
            sccs.append(comp)

    for v in graph:
        if v not in index:
            strongconnect(v)
    return sccs

It is also a trap. Python's default recursion limit is 1,000 frames, and a path of 100,000 vertices, such as a long dependency chain, needs 100,000 nested calls. Raising the limit is fragile and depends on the interpreter version and thread stack size, and Java and C++ simply overflow their stacks. Production code should manage its own stack. The iterative version keeps a work stack of (vertex, edge-iterator) pairs, so each vertex resumes scanning its edges where it left off, and it propagates low-links to the parent when a vertex finishes:

def tarjan_scc(graph):
    """Iterative Tarjan. Returns SCCs in reverse topological order of the condensation."""
    index, low, on_stack, stack, sccs = {}, {}, set(), [], []
    counter = 0
    for root in graph:
        if root in index:
            continue
        index[root] = low[root] = counter; counter += 1
        stack.append(root); on_stack.add(root)
        work = [(root, iter(graph[root]))]     # explicit call stack: (vertex, edge iterator)
        while work:
            v, it = work[-1]
            advanced = False
            for w in it:                       # resumes where this vertex left off
                if w not in index:
                    index[w] = low[w] = counter; counter += 1
                    stack.append(w); on_stack.add(w)
                    work.append((w, iter(graph[w])))
                    advanced = True
                    break
                if w in on_stack:
                    low[v] = min(low[v], index[w])
            if advanced:
                continue
            work.pop()                         # v is finished
            if work:
                parent = work[-1][0]
                low[parent] = min(low[parent], low[v])
            if low[v] == index[v]:
                comp = []
                while True:
                    w = stack.pop(); on_stack.discard(w)
                    comp.append(w)
                    if w == v:
                        break
                sccs.append(comp)
    return sccs

G = {"a": ["b"], "b": ["c", "d"], "c": ["a"], "d": ["e"],
     "e": ["f"], "f": ["d"], "g": ["f", "h"], "h": ["g"]}
print(tarjan_scc(G))   # [['f', 'e', 'd'], ['c', 'b', 'a'], ['h', 'g']]

The line that updates the parent's low-link after the pop is the iterative equivalent of the statement after the recursive call. Forget it and low-links stop flowing up the tree, so components get split incorrectly: on the example, {a, b, c} comes out as {c, b} and {a}, and {d, e, f} splits too.

A traced worked example

Run the iterative code on the graph above, starting at a. The order of events is:

The output is [['f', 'e', 'd'], ['c', 'b', 'a'], ['h', 'g']]. Notice that {d, e, f} came out first even though a was discovered first. Tarjan's algorithm always emits a component only after every component it can reach, so the output is a reverse topological order of the condensation. Reverse the list and you have a valid order in which to process components so that every edge goes forward, with no separate topological sort.

Bugs that break real implementations

• Checking visited instead of on-stack. Writing elif w in index instead of elif w in on_stack lets a cross edge into a finished component lower a low-link. Components get merged or, when the affected vertex is a DFS root, never emitted at all. Graphs that are one big cycle never trigger it; the example's g to f edge does.
• Vertices that appear only as targets. If a vertex has no outgoing edges and is not a key in the adjacency map, graph[w] raises KeyError. Normalise the input so every vertex is a key, even with an empty list.
• Assuming output order. Code that relies on components coming out in topological order instead of reverse topological order produces schedules where a component runs before its dependencies.

Complexity, memory and the alternatives

Each vertex is pushed and popped once, and each edge is examined once, so the running time is O(V + E). Memory is O(V) for index, low, the stack and the work stack, on top of the graph itself.

Depth-first search is hard to parallelise, so distributed systems use forward-backward decomposition instead: the intersection of the set a pivot reaches and the set that reaches it is the pivot's SCC. If you only need to know which vertices are mutually reachable in an undirected graph, you want connected components, and union-find does that incrementally.

Using the output: condensation and 2-SAT

Build the condensation by mapping each vertex to its component id and adding a deduplicated edge for every original edge that crosses components. Because Tarjan's ids follow reverse topological order, iterating ids in ascending order solves every successor before its predecessors. Dynamic programming over a DAG is the usual next step, for example the maximum total weight collectable on a walk when cycles let you revisit vertices freely.

The classic application is 2-satisfiability. Each clause (A or B) is equivalent to two implications, not A implies B and not B implies A. Build the implication graph over 2n literals and find its SCCs. The formula is unsatisfiable exactly when some variable and its negation are in the same SCC. Otherwise, set each variable to true when its positive literal's component comes later in topological order than its negation's, which with Tarjan's numbering means a smaller id:

def two_sat(n, clauses):
    """n boolean variables; clauses are pairs of literals, literal = (var, is_true).
    Returns a satisfying assignment as a list of bools, or None."""
    lit = lambda v, t: 2 * v + (0 if t else 1)          # x_v -> 2v, not x_v -> 2v+1
    graph = {i: [] for i in range(2 * n)}
    for (a, ta), (b, tb) in clauses:                     # (A or B) == (not A -> B) and (not B -> A)
        graph[lit(a, not ta)].append(lit(b, tb))
        graph[lit(b, not tb)].append(lit(a, ta))
    comp = {}
    for cid, scc in enumerate(tarjan_scc(graph)):        # cid follows reverse topological order
        for node in scc:
            comp[node] = cid
    result = []
    for v in range(n):
        if comp[2 * v] == comp[2 * v + 1]:
            return None                                  # x and not-x imply each other
        result.append(comp[2 * v] < comp[2 * v + 1])     # true if x's SCC is later in topo order
    return result

This runs in time linear in the number of clauses.

Testing it

For large graphs, use dense integer ids, adjacency in compressed sparse row arrays and a boolean array for the on-stack flag; dictionaries of lists cost tens of bytes per edge in Python.

Test against a brute-force oracle. For random graphs of 1 to 12 vertices, compute reachability with a BFS from every vertex, derive the mutual-reachability classes, and compare them with Tarjan's output as sets of frozensets. Add a property check that the reversed output is a valid topological order of the condensation, and a stress test with a 1,000,000-vertex path to prove the iterative version does not recurse.

What to do next

1. Implement the iterative version in your language and run the eight-vertex example; confirm you get the three components in the order shown.
2. Write the brute-force oracle test and run it on a few thousand random graphs, including graphs with self-loops, duplicate edges and isolated vertices.
3. Deliberately change the on-stack check to a visited check and watch the oracle test fail, so you know the test covers it.
4. Add the million-vertex path stress test.
5. Build the condensation for a real graph you own, such as package imports or service calls, and list every component with more than one vertex: those are your cycles.
6. Solve a small 2-SAT instance with the code above and verify the assignment satisfies every clause.