AlgoScope

Tarjan SCC

Push on entry, lower low-links through open vertices, pop a whole component when low[u] == disc[u].

Connectivity and topological order, algorithm, advanced
Component 1: 6.00112033435366u
Component 1: 6.00112033435366u

Bridges and Components: Tarjan on two cycles

Decision, step 13 of 24

6 finishes with low[6] = disc[6] = 6: nothing below it reaches an earlier open vertex, so 6 is the root of a component. Pop the stack down to 6: component 1 is {6}.

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.