Strongly Connected Components
A strongly connected component is a maximal set of vertices where every vertex can reach every other; they are found in linear time.
Mutual reachability
In a directed graph, two vertices are strongly connected if each can reach the other along directed edges. A strongly connected component (SCC) is a maximal group of mutually reachable vertices. Contracting each SCC to a single node turns any directed graph into a directed acyclic graph called the condensation, exposing its large-scale structure.
Linear-time algorithms
Two classic algorithms find all SCCs in O(V + E). Kosaraju's runs a depth-first search to order vertices by finish time, reverses every edge, then runs DFS again in that order; each tree in the second pass is one SCC. Tarjan's finds them in a single DFS using low-link values and a stack, which is more efficient in practice.
- Time: O(V + E) for both Kosaraju's and Tarjan's
- SCCs partition the vertices of a directed graph
- The condensation of SCCs is always a DAG
- Tarjan's uses one DFS; Kosaraju's uses two
Low-link intuition
Tarjan's algorithm assigns each vertex a discovery index and tracks the lowest index reachable from its subtree via back edges. When a vertex's low-link equals its own index, it is the root of an SCC, and the component is exactly the vertices sitting above it on the stack.
Where SCCs matter
SCC decomposition solves 2-satisfiability, analyses the structure of the web graph and social networks, finds deadlock cycles in dependency graphs, and preconditions many other algorithms by reducing a cyclic graph to its acyclic skeleton, after which a topological sort becomes possible.