Strongly Connected Components

Definition

A strongly connected component (SCC) of a directed graph $G = (V, E)$ is a maximal subset $C \subseteq V$ such that for every ordered pair of vertices $u, v \in C$, there exists a directed path from $u$ to $v$ and a directed path from $v$ to $u$. In other words, every vertex in the SCC can reach every other vertex within the SCC.

SCCs form a partition of the vertex set: every vertex belongs to exactly one SCC. A singleton vertex with no self-loop is a trivial SCC of size 1. SCCs generalise the notion of connected components from undirected graphs to directed graphs, requiring bidirectional reachability rather than just undirected connectivity.

Worked Example

Directed graph: $V = \{1,2,3,4,5,6,7,8\}$, edges:

$1 \to 2$, $2 \to 3$, $2 \to 4$, $3 \to 1$, $3 \to 4$, $4 \to 3$, $5 \to 4$, $5 \to 6$, $6 \to 5$, $6 \to 7$, $7 \to 8$, $8 \to 6$, $8 \to 7$.

SCC decomposition:

• SCC 1: $\{1, 2, 3, 4\}$. Vertices 1, 2, 3, 4 are all mutually reachable: $1 \to 2 \to 3 \to 1$ forms a directed cycle; $3 \to 4 \to 3$ is another cycle; $2 \to 4$ is within the same SCC since $4 \to 3 \to 1 \to 2$ gives the return path. Edges to vertices outside: $5 \to 4$ enters this SCC.
• SCC 2: $\{5, 6, 7, 8\}$. $5 \to 6 \to 5$ is a cycle; $6 \to 7 \to 8 \to 6$ is another cycle. All four are mutually reachable.

Thus the graph has two SCCs.

The Component Graph

Define the component graph $G^{\text{SCC}} = (V^{\text{SCC}}, E^{\text{SCC}})$:

• Each vertex in $V^{\text{SCC}}$ corresponds to one SCC of $G$.
• A directed edge $C_i \to C_j$ exists iff there is at least one edge $(u, v) \in E$ where $u \in C_i$ and $v \in C_j$ (i.e. there is an edge from some vertex in $C_i$ to some vertex in $C_j$ in the original graph).

Theorem: $G^{\text{SCC}}$ is always a DAG (directed acyclic graph).

Proof: Suppose $G^{\text{SCC}}$ contained a directed cycle $C_1 \to C_2 \to \cdots \to C_k \to C_1$. Then:

• A vertex in $C_1$ can reach a vertex in $C_2$ (by the original graph edges).
• A vertex in $C_2$ can reach a vertex in $C_3$.
• …
• A vertex in $C_k$ can reach a vertex in $C_1$.

By transitivity of reachability, every vertex in $C_1 \cup C_2 \cup \cdots \cup C_k$ can reach every other vertex in this union. But then $\bigcup_{i=1}^k C_i$ would itself be strongly connected, contradicting the maximality of the SCCs (they would have been merged into a single larger SCC). Hence $G^{\text{SCC}}$ is acyclic.

Since the component graph is a DAG, it has at least one source SCC (no incoming edges from other SCCs) and at least one sink SCC (no outgoing edges to other SCCs). It also admits a topological ordering.

Properties

1. SCCs are closed under cycles: Any directed cycle is entirely contained within a single SCC.
2. Condensation: Collapsing each SCC into a single super-node produces the component graph, which is a DAG. Many graph problems become simpler on the condensed graph.
3. DFS and SCCs: DFS on a directed graph assigns finish times that respect the topological ordering of the component graph: vertices in a “downstream” SCC (closer to a sink) finish before vertices in an “upstream” SCC.

Why SCCs Matter

• Cycle analysis: If a graph has cycles, they are contained within SCCs. Reducing the graph to its component DAG reveals the acyclic structure.
• Social networks: Mutual follow groups correspond to SCCs.
• Deadlock detection: In a wait-for graph of processes/resources, cycles indicate deadlocks. The SCC decomposition identifies all deadlocked groups.
• Graph compression: A large graph can be compressed by replacing each SCC with a single representative node.
• Logic and compilation: Dependency graphs for modules or SAT solvers often contain SCCs; collapsing them simplifies analysis.

Algorithms to Find SCCs

Algorithm	Technique	Time
Kosaraju	Two-pass DFS ($G$ then $G^T$)	$\Theta(V+E)$
Tarjan	Single-pass DFS with lowlinks	$\Theta(V+E)$

Only Kosaraju is on the Part IA syllabus. See Kosaraju’s Algorithm for the full treatment.

Relationship with Other Concepts

• Weakly connected components (undirected sense) can span multiple SCCs. SCC is a stricter notion of connectivity.
• DAGs: Every vertex in a DAG is its own SCC (there are no cycles, so no nontrivial mutual reachability). The component graph of a DAG is isomorphic to the DAG itself.
• Topological sort: Works on DAGs. For a general directed graph, topologically sort the component graph, then topologically sort within each SCC (though within an SCC no total order respecting all edges can exist since there are cycles).

Summary

Term	Definition
SCC	Maximal mutually reachable vertex set
Component graph	DAG where each node = one SCC
Condensation	Collapsing SCCs yields DAG
Kosaraju	Two-pass DFS, $\Theta(V+E)$
Key property	$G^{\text{SCC}}$ is always acyclic
DFS property	Finish times reflect component DAG topological order

Past paper questions: SCCs are assessed conceptually; Kosaraju’s steps may appear in open-ended algorithm questions. Also see y2026p1q10 (DAG).