Strongly Connected Components
Partition a directed graph by mutual reachability, replay two-pass DFS and contract its strongly connected components into a DAG.
Free theory articlePartition a directed graph by mutual reachability, replay two-pass DFS and contract its strongly connected components into a DAG.
Concept & interpretation
A directed arrow grants travel in one direction. Two vertices belong to the same strongly connected component, or SCC, exactly when each can reach the other by a directed path. A component is maximal: every vertex mutually reachable with its members is included. A single outgoing route does not establish strong connectivity.