Strongly Connected Components

AlgorithmadvancedConnectivityalso called SCC

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

Decision · step 5 of 24Bridges and Components: Tarjan on two cycles

Edge 2 -> 0: 0 is still on the stack, so it is open and in the same component as 2. low[2] drops to disc[0] = 0.

Open in the player →or start at step 5

What you will see

Each SCC is coloured; the condensation graph is a DAG.

How bridges and components works →

Cost

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

How you work with it here

play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.

Screen readers: Vertices announce name, discovery numbers where relevant and component; each step announces the structural conclusion (bridge found, component closed).

Reduced motion: Component colouring and ordering changes crossfade in place.

Before this

Depth-First Search Directed Graph

Kosaraju Tarjan SCC

Leads to

Topics that need this one first.

Kosaraju Tarjan SCC

Taught by the same lesson

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

Articulation Points Bridges Kosaraju Tarjan SCC