Strongly Connected Components
Maximal sets where every vertex reaches every other. The condensation is a DAG.
Bridges and Components: Tarjan on two cycles
3 strongly connected components, coloured by membership. Each was popped the moment its root finished, so the components come out in reverse topological order of the condensed graph. One DFS, O(V + E).
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Bridges and Components covers these too, in the same run.