Strongly Connected Components
Group mutually reachable nodes with Tarjan.
What an SCC Is
A strongly connected component is a maximal group of nodes where every node can reach every other by following directed edges.
Why We Care
Collapsing each SCC into one supernode turns any directed graph into a DAG. That makes mutual dependencies easy to reason about.
All lessons in this course
- Topological Sort with Kahn's Algorithm
- Detect Cycles in Directed Graphs
- Strongly Connected Components
- Bridges & Articulation Points