Strongly Connected Components (SCC)

Decomposition of a directed graph into maximal mutually reachable sets; condensation graph reveals high-level dependency DAG.

Overview

A strongly connected component (SCC) in a directed graph is a maximal set of vertices mutually reachable. Collapsing each SCC yields a DAG (condensation graph).

Graph

Directed

Output

Component sets

Condensation

DAG

Definition

u and v are strongly connected if u→v and v→u (path-wise).
SCC partitions vertex set.
Resulting condensation graph is acyclic.

Algorithms

Kosaraju: DFS order + transpose DFS.
Tarjan: Single DFS with stack & lowlink.
Gabow: Two stacks variant.

Applications

Cycle detection & grouping
Program module dependency condensation
2-SAT implication graph components
Deadlock / strongly coupled system analysis

Complexity

Kosaraju

O(n+m)

Tarjan

O(n+m)

Space

O(n)

Linear time: each edge & vertex processed constant number of times.

Comparison

Algorithm	Passes	Key Structure	When Preferred
Kosaraju	2 DFS + transpose	Stack (finish order)	Clarity, teaching
Tarjan	1 DFS	Lowlink + stack	Performance simplicity
Gabow	1 DFS	Two stacks	Alternate lowlink avoidance

Quick Facts

Output Form: Partition of V
Condensation: Always DAG
Edge Types: All directed edges processed
2-SAT: Uses SCC + implications

Next Steps

Learn the two-pass Kosaraju process and lowlink intuition for Tarjan, then animate SCC discovery.

Theory Simulation All Graph Algorithms

Back: topological-sort