SCCs, Bridges and Articulation Points
One DFS with low-link values finds strongly connected components in a directed graph, and bridges and cut vertices in an undirected one.
The problem
Two questions about a graph, one tool.
- Directed graph. Which vertices can reach each other in both directions? Such a group is a strongly connected component (SCC): a maximal set where every vertex reaches every other.
- Undirected graph. Which single road is critical, so that closing it splits the network? That edge is a bridge. A vertex with the same property is an articulation point (cut vertex).
1 of 9