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.
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
Worked example
- If
a → b → c → a, thena, b, clie in one SCC because each reaches the others. - If there is an edge
c → dbut no path back fromdtoa, thendis 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Lazy Propagation for Range Updates and Range Queries.
Least You Need to Know: Lazy Propagation for Range Updates and Range QueriesRelated lessons
Keep going with nearby lessons in the same topic.