Tarjan SCC

Finds strongly connected components — maximal groups where every vertex can reach every other — in a single depth-first pass. Each vertex tracks a "low-link": the earliest vertex reachable by descending and then taking at most one back-edge. A vertex whose low-link equals its own index is the root of a component.

Best

O(V+E)

Average

O(V+E)

Worst

O(V+E)

Space

O(V)