Strongly Connected Components - Algorithm Tutorial | Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Introduction

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

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:

Run DFS on the original graph, recording finish times
Transpose the graph (reverse all edges)
Run DFS on the transposed graph in decreasing order of finish times
Each DFS tree in step 3 is an SCC

text

function kosaraju(n, edges):
    graph = build_graph(edges)
    transposed = build_transposed(edges)

    // Pass 1: Record finish order
    visited = array of false
    finish_order = []
    for v from 1 to n:
        if not visited[v]:
            dfs1(v, graph, visited, finish_order)

    // Pass 2: Count SCCs
    visited2 = array of false
    scc_count = 0
    for v in reverse(finish_order):
        if not visited2[v]:
            scc_count++
            dfs2(v, transposed, visited2)

    return scc_count

Why Kosaraju Works

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.

text

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.

Strongly Connected Components Algorithm Tutorial

Introduction

Kosaraju's Algorithm

Why Kosaraju Works

Tarjan's Algorithm

Implement this Algorithm

Related Algorithms

Complexity and Variations