Graph Algorithms9 min read

Tarjan's Algorithm

Find all tightly-knit groups in a directed graph in one pass
time:\(O(V+E)\)space:\(O(V)\)output:All SCCs in one DFS

Think about a social network where some groups of friends are so tightly connected that everyone can reach everyone else — directly or through mutual friends. These are cliques of mutual reachability. In a directed graph, we call them Strongly Connected Components (SCCs).

Formally: an SCC is a maximal set of vertices where for every pair u and v, there's a directed path from u to v AND from v to u. Tarjan's algorithm finds all SCCs in a single depth-first search — no need to traverse the graph twice or build a transposed copy.

Discovery and Low-Link Values

Tarjan's DFS tracks two numbers per vertex:

  • disc[u] — the DFS discovery time (a clock that ticks up each time we visit a new vertex)
  • low[u] — the lowest discovery time reachable from u's DFS subtree via tree edges and at most one back edge (an edge to an ancestor still on the DFS stack)

Initially low[u] = disc[u]. As DFS explores neighbors:

  • If neighbor v is unvisited: recurse, then set low[u] = min(low[u], low[v])
  • If neighbor v is on the DFS stack (a back edge): set low[u] = min(low[u], disc[v])

The Stack and SCC Detection

Every vertex is pushed onto an auxiliary stack when first visited. The key insight: when DFS finishes a vertex u (all its descendants are done), check if low[u] == disc[u].

If yes, u is the root of an SCC — no path from u's subtree escapes to an ancestor. Pop everything from the stack down to and including u — that's one complete SCC.

If low[u] < disc[u], some descendant of u can reach an ancestor of u, so u is not the root of its own SCC — it belongs to a larger component.

What the Condensation DAG Reveals

Once all SCCs are found, replace each SCC with a single super-node. The resulting graph — the condensation DAG — is always acyclic (since cycles within components were already collapsed). This DAG captures the high-level structure: which components can reach which others. It's the foundation for further algorithms like topological sort on the component level.

Extensions: Bridges and Articulation Points

The same DFS framework works on undirected graphs to find:

  • Bridge: edge (u, v) is a bridge if low[v] > disc[u] — removing it disconnects the graph
  • Articulation point: vertex u is an articulation point if removing it disconnects the graph (different condition for root vs. non-root)

All of these can be found in the same single DFS pass — \(O(V+E)\) total.

Note: low[u] answers the question: 'Can any vertex in my DFS subtree sneak a back edge to reach an ancestor?' If low[u] == disc[u], the answer is no — u and its subtree form a sealed-off group with no way out. That sealed group is an SCC.

Tarjan's SCC Algorithm

def tarjans_scc(n, adj):
    """
    n: number of vertices
    adj: adjacency list
    Returns list of SCCs (each SCC is a list of vertex indices).
    """
    disc = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    timer = [0]


    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True


        for v in adj[u]:
            if disc[v] == -1:       # unvisited
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:       # back edge to ancestor
                low[u] = min(low[u], disc[v])


        if low[u] == disc[u]:       # u is SCC root
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == u:
                    break
            sccs.append(scc)


    for u in range(n):
        if disc[u] == -1:
            dfs(u)
    return sccs


# Graph: 0->1, 1->2, 2->0, 1->3, 3->4, 4->5, 5->3
adj = [[1],[2,3],[0],[4],[5],[3]]
sccs = tarjans_scc(6, adj)
for scc in sccs:
    print(sorted(scc))
Output
[3, 4, 5]
[0, 1, 2]

Complexity

🔍 SCC findingSingle DFS pass — each vertex and edge processed exactly once
Linear in graph size\(O(V+E)\)
💾 Space (stack + arrays)disc[], low[], onStack[], and the auxiliary stack — all \(O(V)\)
Proportional to vertices\(O(V)\)
🌉 Bridge findingCheck low[v] > disc[u] for each tree edge (u,v) during the same traversal
Same single DFS\(O(V+E)\)
🔗 Articulation pointsSlightly different condition from bridges but found in the same single pass
Same single DFS\(O(V+E)\)

Quick check

What exactly does low[u] represent in Tarjan's algorithm?

Continue reading

Kosaraju's Algorithm
Find mutual-follow groups with two clever graph walks
→
BFS & DFS Revisited
Two ways to explore a graph — level by level, or all the way in
→
Eulerian Path & Circuit
Can you cross every bridge exactly once? Euler answered this in 1736
→