Algorithms / Scc
Least You Need to Know: Strongly Connected Components and Mutual Reachability
A strongly connected component in a directed graph is a maximal set of vertices that can all reach one another. SCCs reveal the graph's cyclic cores and compress repeated mutual-reachability structure into components.
The least you need to know
- SCCs are defined for directed graphs, not undirected connectivity.
- Within one SCC, every vertex can reach every other vertex.
- Maximal means no extra vertex can be added without breaking that property.
- Kosaraju and Tarjan both find SCC structure in linear time.
- Contracting SCCs exposes a higher-level acyclic structure.
Key notation
u ↝ v
there exists a directed path from u to v
SCC
maximal set with pairwise mutual reachability
transpose graph
graph with every edge direction reversed
Tiny worked example
- If `a → b → c → a`, then `a, b, c` lie in one SCC because each reaches the others.
- If there is an edge `c → d` but no path back from `d` to `a`, then `d` is outside that SCC.
- SCC decomposition groups the cycle together and keeps one-way outgoing structure separate.
- That grouping is the right abstraction for many reachability and condensation arguments.
Common mistakes
- Students often confuse SCCs with weak connectivity after ignoring edge directions.
- A directed cycle implies one SCC, but SCCs can contain more than one cycle.
- Maximality matters: a mutually reachable subset may sit inside a larger SCC.
How to recognize this kind of problem
- The problem asks which directed vertices can all reach each other.
- Cycles and one-way component dependencies both matter.
- A condensation DAG or SCC compression is mentioned.