Workspace

Problem workspace

3 day streakD

Tarjan’s SCC Algorithm

HardGraphsConnectivity

The challenge

Find all strongly connected components of a directed graph in one DFS using discovery indices, low-link values, and a stack of vertices not yet assigned to a component.

The SCC stack is different from the recursion stack: a returned vertex can remain on it until its SCC root finishes.

Example

The SCCs are {E}, {C, D}, and {A, B, F}; their output order can differ from Kosaraju’s while the partition is identical.

Use the walkthrough below to inspect the input and each state change.

See Tarjan SCC, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 7 edgesA = 0, B = 1, …
Three SCCsDirected graph with 6 vertices. Initialize discovery and low-link values. Discovery is the DFS entry index. Low-link tracks the earliest active SCC candidate reachable through the DFS subtree. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Discovery / low-link
ABCDEF
——————
Step 01 / 18

Initialize discovery and low-link values.

Discovery is the DFS entry index. Low-link tracks the earliest active SCC candidate reachable through the DFS subtree.

discovery = [-1] * V; timer = 0

SCC stack · top last

Empty
View input edges

A → B · B → F · F → A · B → C · C → D · D → C · D → E

Put it into code

A vertex with low[u] = index[u] is the root of a complete SCC.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def tarjan_scc(adj):
    n = len(adj)
    index, low = [-1] * n, [-1] * n
    stack, on_stack, components = [], [False] * n, []
    timer = 0

    def visit(u):
        nonlocal timer
        index[u] = low[u] = timer
        timer += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if index[v] == -1:
                visit(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], index[v])
        if low[u] == index[u]:
            component = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                component.append(v)
                if v == u:
                    break
            components.append(component)

    for u in range(n):
        if index[u] == -1:
            visit(u)
    return components

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap