Tarjan's strongly connected components algorithm in Python

A single DFS with a stack and low-link values finds all SCCs in linear time.

File: tarjan_scc.py, 60 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

tarjan_scc.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tarjan-scc/. The authors are listed in prov/JH9ZVM.jsonl.


def tarjan_scc(adj: list[list[int]]) -> list[int]:
    """Return comp, where comp[v] is the number of the strongly connected component of v.

    The graph is directed, with vertices 0 .. n-1 and adjacency lists adj. Parallel
    arcs (repeated entries) and self-loops (v in adj[v]) are allowed. The components
    are numbered 0, 1, ... in the order their roots finish, which is a reverse
    topological order of the condensation: for each arc (u, v), comp[u] >= comp[v].
    The recursion of STRONGCONNECT is replaced by an explicit stack of frames
    (v, i), where i is the position of the next arc of v to scan.
    Time O(n + m), extra space O(n).
    """
    n = len(adj)
    index = [-1] * n  # @line L1
    low = [0] * n
    on_stack = [False] * n
    stack: list[int] = []
    comp = [-1] * n
    counter = 0
    k = 0
    call: list[tuple[int, int]] = []

    def enter(v: int) -> None:
        nonlocal counter
        index[v] = low[v] = counter  # @line L5
        counter += 1
        stack.append(v)  # @line L6
        on_stack[v] = True
        call.append((v, 0))

    for u in range(n):  # @line L2
        if index[u] != -1:  # @line L3
            continue
        enter(u)
        while call:
            v, i = call[-1]
            if i < len(adj[v]):
                call[-1] = (v, i + 1)
                w = adj[v][i]  # @line L7
                if index[w] == -1:  # @line L8
                    enter(w)  # @line L9
                elif on_stack[w]:  # @line L10
                    low[v] = min(low[v], index[w])
                continue
            call.pop()  # STRONGCONNECT(v) ends here
            if low[v] == index[v]:  # @line L11
                while True:  # @line L12
                    w = stack.pop()  # @line L13
                    on_stack[w] = False
                    comp[w] = k
                    if w == v:
                        break
                k += 1  # @line L14
            if call:  # back in the parent p: the second half of line L9
                p = call[-1][0]
                low[p] = min(low[p], low[v])
    return comp  # @line L4

test_tarjan_scc.py 76 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tarjan-scc/. The authors are listed in prov/JH9ZVM.jsonl.

import random

from tarjan_scc import tarjan_scc


def reach(adj: list[list[int]], s: int) -> set[int]:
    seen, todo = {s}, [s]
    while todo:
        u = todo.pop()
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                todo.append(v)
    return seen


def check(adj: list[list[int]]) -> None:
    n = len(adj)
    comp = tarjan_scc(adj)
    r = [reach(adj, u) for u in range(n)]
    for u in range(n):
        for v in range(n):
            assert (comp[u] == comp[v]) == (v in r[u] and u in r[v])
    for u in range(n):
        for v in adj[u]:
            assert comp[u] >= comp[v]
    if n:
        assert sorted(set(comp)) == list(range(max(comp) + 1))


def test_example() -> None:
    adj = [[1, 3, 2], [2], [0], [2, 4], [], [4, 6], [5]]
    assert tarjan_scc(adj) == [1, 1, 1, 1, 0, 2, 2]


def test_edges() -> None:
    assert tarjan_scc([]) == []
    assert tarjan_scc([[]]) == [0]
    assert tarjan_scc([[0]]) == [0]
    assert tarjan_scc([[0, 0, 1], [1]]) == [1, 0]
    assert tarjan_scc([[1, 1], [0]]) == [0, 0]
    assert tarjan_scc([[1], [2], []]) == [2, 1, 0]
    assert tarjan_scc([[], [0], [1]]) == [0, 1, 2]
    cycle = [[(i + 1) % 6] for i in range(6)]
    assert tarjan_scc(cycle) == [0] * 6
    # undirected graph given with both arcs: components are connected components
    assert tarjan_scc([[1], [0], [3], [2]]) == [0, 0, 1, 1]


def test_cross_arc_to_stack() -> None:
    # 0 -> 1 -> 0 and 0 -> 2 -> 1: the cross arc 2 -> 1 goes to a vertex on the stack
    assert tarjan_scc([[1, 2], [0], [1]]) == [0, 0, 0]
    # cross arc 2 -> 1 into a finished component {1}
    assert tarjan_scc([[1, 2], [], [1]]) == [2, 0, 1]


def test_long_path() -> None:
    n = 20000
    path = [[i + 1] for i in range(n - 1)] + [[]]
    assert tarjan_scc(path) == list(range(n - 1, -1, -1))
    path[-1] = [0]
    assert tarjan_scc(path) == [0] * n


def test_random() -> None:
    rng = random.Random(21)
    for _ in range(600):
        n = rng.randrange(1, 9)
        m = rng.randrange(0, 3 * n)
        adj: list[list[int]] = [[] for _ in range(n)]
        for _ in range(m):
            adj[rng.randrange(n)].append(rng.randrange(n))
        check(adj)

What the next level needs

the tests did not run in this build

Read the full page about Tarjan's strongly connected components algorithm