AlgoScope

Strongly Connected Components

Maximal sets where every vertex reaches every other. The condensation is a DAG.

Connectivity and topological order, algorithm, advancedAlso called SCC
3 components.00102033435366
3 components.00102033435366

Bridges and Components: Tarjan on two cycles

Result, step 24 of 24

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).

How bridges and components works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Leads to

Topics that need this one first.

Taught by the same lesson

Bridges and Components covers these too, in the same run.