Strongly Connected Components (SCC)

Lecture slides (PDF)

A strongly connected component (SCC) of a directed graph is a maximal set of vertices $S \subseteq V$ such that for every pair of vertices $u, v \in S$, there is a directed path from $u$ to $v$ and from $v$ to $u$.

We want to compute these strongly connected components of a directed graph.


Recall that a directed acyclic graph (DAG) is a directed graph with no directed cycles.

Observation 1: If we contract each SCC into a single vertex, the resulting contracted graph is a DAG.

Proof: Suppose for contradiction the contracted graph has a directed cycle $X_1 \to X_2 \to \cdots \to X_k \to X_1$. Then every vertex in $X_1$ can reach every vertex in $X_k$ (through $X_2, \ldots, X_{k-1}$), and vice versa. This makes $X_1 \cup \cdots \cup X_k$ strongly connected, contradicting the maximality of each $X_i$ as an SCC.

The contracted graph of the example above is:

The sink of the contracted graph is a component with no outgoing edges to other components in the contracted graph. The source of the contracted graph is a component with no incoming edges from other components in the contracted graph. Note that we might have more than one source or sink in the contracted graph.

For example, in the above, $D$ is a sink.


Idea: Identify a vertex in a sink SCC. Run DFS from that vertex which will only explore vertices in that sink SCC, allowing us to identify all vertices in that SCC. This is because there is no edge going out of a sink. Delete the vertices in that SCC from the graph and repeat the process on the remaining graph to identify all SCCs.

For example, if we run DFS from 13 in the example graph, we will visit 13, 14, and 12, which are exactly the vertices in the sink SCC $D$. Then we delete these vertices from the graph and repeat the process on the remaining graph to identify the other SCCs. The challenge is however how to efficiently find a vertex in a sink SCC without knowing the SCCs in advance.


Observation 2: If SCC $X$ is before SCC $Y$ in the contracted DAG (i.e., there is a path from $X$ to $Y$ in the contracted graph), then the maximum post number of any vertex in $X$ is greater than the maximum post number of any vertex in $Y$.

Proof: Consider a DFS traversal. There are two cases:

Case 1: DFS enters $X$ before $Y$. Since there is a path from $X$ to $Y$ in the contracted DAG, when DFS visits any vertex in $X$, it will eventually reach $Y$ (either directly or through intermediate components) before finishing that vertex. Therefore, all vertices in $Y$ are discovered and finished before any vertex in $X$ finishes. This means every vertex in $Y$ has a smaller post number than every vertex in $X$.

Case 2: DFS enters $Y$ before $X$. Since the contracted graph is a DAG with a path from $X$ to $Y$, there cannot be a path from $Y$ to $X$. If DFS starts in $Y$ and never reaches $X$ (which it can’t, since no path exists from $Y$ to $X$), then $Y$ is fully explored before DFS ever visits $X$. In this case, all vertices in $Y$ finish before any vertex in $X$ is even discovered. Again, every vertex in $Y$ has a smaller post number than every vertex in $X$.

In both cases, we have $\max_{v \in X} \text{post}[v] > \max_{w \in Y} \text{post}[w]$.


If we run DFS on the above graph starting from vertex $1$ and at each step explore the next unvisited vertex in numerical order, the pre and post numbers of each vertex are as shown in the figure below:


This suggests that the vertex with the largest post number in a DFS of the original graph must lie in a source SCC of the contracted DAG. However, what we want is a vertex in a sink SCC of the contracted DAG. This is the third key observation.

Observation 3: If we reverse all edges in the original graph to get the transpose graph $G^T$, the SCCs stay the same. Furthermore, the sink SCCs of the original graph become source SCCs in $G^T$.


This suggests the following algorithm:

  1. Run DFS on $G$.
  2. Run DFS on $G^T$ processing vertices in decreasing order of post numbers from step 1. Each DFS tree in this second pass is an SCC.

Step 1: DFS from vertex 1 (largest post number in $G$) on $G^T$ reaches only ${1,2,3,4,5}$ — SCC $A$ identified.

Step 2: Remove SCC $A$. DFS from vertex 6 (next largest unvisited post number) reaches ${6,7,8,9}$ — SCC $B$ identified.

Step 3: Remove SCC $B$. DFS from vertex 10 reaches ${10,11}$ — SCC $C$ identified.

Step 4: Remove SCC $C$. DFS from vertex 13 reaches ${12,13,14}$ — SCC $D$ identified.

The algorithm involves two DFSs and constructing $G^T$, all of which take $O(V+E)$ time, so the overall time complexity of finding all strongly connected components is $O(V+E)$.


To be concrete, the Julia implementation is shown below:

function strongly_connected_components(n, adj)
    # Step 1: DFS on G to get post order
    visited = falses(n)
    post_order = Int[]

    function dfs1(v)
        visited[v] = true
        for w in adj[v]
            if !visited[w]
                dfs1(w)
            end
        end
        push!(post_order, v)
    end

    for v in 1:n
        if !visited[v]
            dfs1(v)
        end
    end

    # Step 2: Build transpose graph G^T
    adj_t = [Int[] for _ in 1:n]
    for u in 1:n
        for v in adj[u]
            push!(adj_t[v], u)
        end
    end

    # Step 3: DFS on G^T in decreasing post order
    fill!(visited, false)
    scc_id = zeros(Int, n)
    num_scc = 0

    function dfs2(v, id)
        visited[v] = true
        scc_id[v] = id
        for w in adj_t[v]
            if !visited[w]
                dfs2(w, id)
            end
        end
    end

    for v in reverse(post_order)
        if !visited[v]
            num_scc += 1
            dfs2(v, num_scc)
        end
    end

    return num_scc, scc_id
end