Implementing Tarjan’s Algorithm for Strongly Connected Components

A directed graph can contain groups of vertices where every vertex is reachable from every other vertex in the same group. These groups are called strongly connected components, or SCCs. They appear whenever relationships have a direction and cycles matter, such as website links, software dependencies, build systems, and state-transition models.

Tarjan’s algorithm finds all SCCs in a single depth-first search. It records the discovery order of each vertex, tracks the earliest reachable ancestor, and uses a stack to keep vertices that belong to the current unresolved component. The result is efficient enough for large sparse graphs and compact enough to implement in Python, C, or another general-purpose language.

This technique is useful beyond textbook graph exercises. A dependency analyser for a Melbourne software team, a service map for an Australian telecommunications provider, or a model of links between ASX-listed companies can all contain cycles. Identifying those cycles helps separate independent regions of a directed graph from tightly connected groups that need to be analysed together.

Why Strongly Connected Components Matter

In an undirected graph, a connected component means that paths exist between vertices without considering direction. A directed graph requires a stricter definition: vertices belong to the same strongly connected component when each can reach every other by following edge directions. A single isolated vertex is also an SCC, even when it has no edges.

Consider the directed edges A → B, B → C, and C → A. These three vertices form one component because each vertex can eventually reach the other two. If there is also an edge C → D, but no path returns from D, then D belongs to a separate component. The edge connects two components, while the cycle remains contained in the first.

SCCs can expose circular imports, mutually dependent packages, and loops in workflow graphs. They are also used to condense a directed graph into a directed acyclic graph, called the condensation graph. Once every SCC is replaced by one super-vertex, cycles disappear between components, making topological processing possible.

An adjacency list is a natural representation for this task because Tarjan’s algorithm visits outgoing neighbours repeatedly. The data structures guide provides useful background on adjacency lists, stacks, and graph storage choices. For a graph with V vertices and E edges, an adjacency list normally uses O(V + E) memory.

Core Invariants Behind Tarjan’s Method

Tarjan’s method assigns each visited vertex an integer called index. This value records the order in which depth-first search first discovers the vertex. It also assigns a lowlink value, which is the smallest discovery index reachable from that vertex while staying within the current DFS structure and using at most one suitable back edge.

At the beginning, a vertex has lowlink[v] = index[v]. During the search, the algorithm examines every outgoing edge v → w. If w has not been visited, DFS explores w first, then updates lowlink[v] with lowlink[w]. If w is already on the stack, the edge can lead back to an active ancestor, so lowlink[v] is updated with index[w].

The stack is essential because a visited vertex does not always belong to the current SCC. A vertex that has already been removed from the stack belongs to a completed component and must not influence the lowlink calculation of a later search branch. An on_stack set, or a Boolean array, makes this distinction explicit.

When lowlink[v] == index[v], vertex v is the root of an SCC. The algorithm pops vertices from the stack until it removes v. Every popped vertex belongs to the same component. This condition is subtle: comparing lowlink[v] with index[v] identifies the root, while comparing lowlink values between arbitrary vertices would not reliably identify component membership.

Python Implementation

The implementation below accepts a list of adjacency lists and returns SCCs as lists of vertex numbers. Vertices are numbered from 0 to n - 1. The outer loop is important because the graph may contain several disconnected regions, and a DFS started from one vertex cannot reach every component.

def tarjan_scc(graph):
    n = len(graph)
    index = 0
    indices = [-1] * n
    lowlink = [0] * n
    stack = []
    on_stack = [False] * n
    components = []

    def strongconnect(v):
        nonlocal index

        indices[v] = index
        lowlink[v] = index
        index += 1

        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if indices[w] == -1:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:
                lowlink[v] = min(lowlink[v], indices[w])

        if lowlink[v] == indices[v]:
            component = []

            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)

                if w == v:
                    break

            components.append(component)

    for vertex in range(n):
        if indices[vertex] == -1:
            strongconnect(vertex)

    return components

For example, the graph

graph = [
    [1],       # 0 -> 1
    [2, 3],    # 1 -> 2 and 3
    [0],       # 2 -> 0
    [4],       # 3 -> 4
    [3]        # 4 -> 3
]

print(tarjan_scc(graph))

contains two SCCs: {0, 1, 2} and {3, 4}. The exact order of components can vary according to traversal order, but the membership of each component should remain the same.

The nested function uses nonlocal index so that every discovery receives the next global index. The recursive call explores an unvisited neighbour. The elif on_stack[w] branch handles an edge to an active vertex, while edges to completed components are deliberately ignored.

Testing And Complexity

A reliable test suite should include an empty graph, a graph containing one vertex, a graph with no edges, a simple directed cycle, several disconnected cycles, and a directed acyclic graph. In an acyclic graph, every vertex should appear in its own SCC because no pair of distinct vertices can reach one another in both directions.

Self-loops deserve a specific test. A vertex with an edge to itself is strongly connected with itself, but that does not automatically connect it to any other vertex. Duplicate edges should also be harmless: they may be examined more than once, yet they do not change the component structure.

The algorithm processes each vertex and edge a constant number of times. Its time complexity is therefore O(V + E), and its auxiliary space complexity is O(V), excluding the input adjacency list. This is asymptotically optimal for a representation where every edge may need to be inspected.

Python’s recursive implementation has a practical limitation. A graph shaped like a long chain can exceed the default recursion limit, even though the algorithm itself is efficient. For controlled educational examples, sys.setrecursionlimit may help, but production code handling untrusted or very deep graphs should use an iterative DFS version or implement the call stack explicitly.

Extensions And Practical Use

After finding the components, it is often useful to build the condensation graph. Assign each original vertex a component identifier, then add an edge from component a to component b whenever an original edge crosses between them. Ignore edges where a == b. The resulting graph is a DAG, so dynamic programming and topological sorting become available.

This transformation is useful in build systems. Suppose a project used across Sydney and Perth has packages that import one another through several layers. Tarjan’s algorithm can identify circular dependency groups, while the condensation graph reveals the order in which independent groups can be compiled or reviewed.

The same idea applies to data-processing pipelines and machine-learning workflows. A cycle may indicate that a feature depends indirectly on its own output, causing a leakage or scheduling problem. A graph analysis can locate the cycle before model evaluation; separate modelling choices, such as those discussed in this regularization review, address overfitting rather than dependency structure.

In Australian infrastructure, directed service graphs can represent traffic between cloud regions, payment systems, NBN-related applications, or transport information services in Brisbane and Adelaide. SCC detection helps identify clusters that can fail together or require coordinated deployment. For large inputs, the linear complexity of Tarjan’s algorithm makes it a strong choice when the graph must be scanned once and memory usage needs to remain predictable.