Condensation — where it appears
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Also named here as directed graph, strongly connected components — the same set of essays touches all of them, so they are one junction rather than several.
Two passes or one, and what the second one costs
Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.
A graph is as hard as its largest cycle
Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.
Named alongside it
The objects these essays reach for when they reach for this one.
Counted primitiveDirected graphStrongly connected componentsTopological sortBellman–FordComplexity classDepth-first searchDirected acyclic graphEarly exitMeasured countNegative weightRelaxation