Strongly Connected Components - Algorithm Tutorial | Repovive

A Strongly Connected Component (SCC) in a directed graph is a maximal set of vertices where every vertex is reachable from every other vertex.

Example: In a social network where edges represent "follows," an SCC represents a group where everyone can see everyone else's content through some chain of follows.

Properties:

Every vertex belongs to exactly one SCC
SCCs partition the vertices of the graph
The graph of SCCs (condensation graph) is always a DAG

Applications:

Finding circular dependencies in software modules
Analyzing strongly connected networks
Computing the 2-SAT satisfiability problem
Model checking in formal verification

Kosaraju's algorithm finds all SCCs in $O(n + m)$ time using two DFS passes.

Idea: If we process vertices in the right order, a single DFS from a vertex will visit exactly its SCC and nothing else.

Algorithm:

The key insight is about the relationship between SCCs and finish times.

Observation 1: If there is an edge from SCC $A$ to SCC $B$ (but not vice versa), then the last vertex to finish in $A$ finishes after the last vertex in $B$ .

Observation 2: In the transposed graph, edges between SCCs are reversed. So if $A$ had an edge to $B$ , now $B$ has an edge to $A$ .

Why it works:

After Pass 1, vertices are ordered by decreasing finish time
The first vertex in this order belongs to a "source" SCC in the condensation
In the transposed graph, this SCC becomes a "sink"
DFS from this vertex visits exactly this SCC (cannot escape to other SCCs)
After marking this SCC, repeat for the next unvisited vertex

Example: If Pass 1 gives finish order [5, 3, 4, 2, 1], we try DFS from 5, then 3, etc. Each DFS finds exactly one SCC.

Tarjan's algorithm is an alternative that finds SCCs in a single DFS pass.

It uses the concept of low-link values: for each vertex, track the earliest vertex reachable through the DFS tree and back edges.

function tarjan(n, edges):
    index = 0
    ids = array of -1
    low = array of 0
    on_stack = array of false
    stack = []
    scc_count = 0

    function dfs(v):
        ids[v] = low[v] = index++
        stack.push(v)
        on_stack[v] = true

        for each neighbor w of v:
            if ids[w] == -1:
                dfs(w)
                low[v] = min(low[v], low[w])
            else if on_stack[w]:
                low[v] = min(low[v], ids[w])

        if ids[v] == low[v]:  // Root of SCC
            scc_count++
            repeat:
                w = stack.pop()
                on_stack[w] = false
            until w == v

    for v from 1 to n:
        if ids[v] == -1:
            dfs(v)

    return scc_count

Both algorithms have the same complexity, but Tarjan's uses less memory and only needs one pass.

Time Complexity: $O(n + m)$ for both algorithms

Each vertex is visited once per DFS pass
Each edge is examined once per pass
Kosaraju: 2 passes = $O(2(n + m)) = O(n + m)$
Tarjan: 1 pass = $O(n + m)$

Space Complexity: $O(n + m)$

$O(n + m)$ for storing the graph
$O(n)$ for visited arrays and stack
Tarjan needs slightly less auxiliary space

Variations:

Find the SCCs themselves: Instead of counting, store which SCC each vertex belongs to
Condensation graph: Build the DAG of SCCs (useful for reachability)
2-SAT: Model implications as edges; SCC analysis determines satisfiability

Related problems:

Bridges and articulation points (for undirected graphs)
Topological sort of the condensation graph
Shortest path between SCCs

Strongly Connected Components Algorithm Tutorial

Introduction

Kosaraju's Algorithm

Practice this Algorithm

Related Algorithms

Why Kosaraju Works

Tarjan's Algorithm

Complexity and Variations