In Kosaraju's algorithm, why does the second pass use the reversed graph in decreasing finish order?
answer
- what does finishing last tell you
- the last finisher sits in a source
- sources reach others, sinks reach nothing
- flipping edges turns a source into a sink
- each restart is trapped in one component
basics
~20 sThe vertex finishing last in the first pass lies in a source component nothing else reaches. Reversing every edge turns that source into a sink, so a traversal started there is trapped inside one component and cannot leak outward.
solid answer
~50 sThe first depth-first pass records finish times. The key lemma is that if an edge runs from component `C` to component `D`, then the largest finish time in `C` exceeds the largest in `D` — so ordering components by their maximum finish time descending is a topological order of the condensation. Now reverse every edge. Cross-component edges now point *backwards*, into components already processed. Starting a traversal at the highest unassigned finish time therefore lands in a component whose only outward edges in the reversed graph lead to vertices that are already labelled, so the traversal collects exactly that component and stops. Each restart peels off one component, giving O(V + E) overall: one pass, one transpose build, one more pass. Drop either ingredient — the order or the reversal — and a single traversal can swallow several components at once.
code
pseudocode · 15 lines# pass 1: list vertices in order of DFS finish time on G
order = empty list
visited = all false
for v in 0..n-1
if not visited[v]
dfs_mark(v) # ... on finishing a vertex, append it to order
# build the transpose: every edge u -> w becomes w -> u
GT = reverse_all_edges(G)
# pass 2: peel one component per restart, in decreasing finish order
comp = all -1
c = 0
for v in reverse(order)
if comp[v] == -1
dfs_assign(v, c) # ... on GT, label every unlabelled vertex reached
c = c + 1go deeper
Know the shape: one traversal to get a finish order, reverse the edges, a second traversal in reverse finish order, and each restart yields one component. Remember it is linear overall.
Explain why both ingredients matter — the last-finishing vertex sits in a source component, and reversal turns that source into a sink so the traversal cannot escape. Be able to say what breaks if either is dropped.
Be ready to justify picking the two-pass method or the one-pass low-link method on constants and memory rather than asymptotics, and to note that recursion depth in either can reach the vertex count.
Own the tradeoff between a method a whole team can re-derive on a whiteboard and one that is a single sweep but easy to get subtly wrong. Argue when the extra reversed edge list is an acceptable price for reviewability.
## The algorithm in outline Kosaraju's method finds all strongly connected components with two depth-first sweeps and one reversed copy of the graph: 1. Run depth-first search over `G`, pushing each vertex onto a list **when it finishes** (after all its descendants are done). 2. Build the transpose `G^T` — the same vertices, every edge flipped. 3. Walk the finish list **backwards**. For each still-unlabelled vertex, run a traversal on `G^T`; everything it reaches that is still unlabelled forms one component. Each step is linear, so the whole thing is O(V + E) with a small constant factor of roughly two traversals plus the transpose build. ## Why finish time orders the components Here is the load-bearing lemma. Let `C` and `D` be distinct components with an edge from some vertex of `C` to some vertex of `D` (so `C -> D` in the condensation). Then > max finish time in `C` > max finish time in `D`. Sketch: if the first pass enters `C` before `D`, the traversal from that vertex of `C` descends into `D`, finishes all of `D` first, and only then finishes back up through `C` — so `C`'s maximum is later. If it enters `D` first, it finishes all of `D` before ever touching `C`, because no path leads back from `D` to `C` (there is none — a return path would merge the two components). Either way `C` finishes later. Sort the components by maximum finish time, descending, and you get a **topological order of the condensation**: every component appears before the components it points to. The vertex with the single largest finish time in the whole graph therefore lies in a **source** component — one no other component can reach. ## Why the reversal is the other half Suppose you did the second pass on `G` itself, in decreasing finish order. You would start in a source component and the traversal would walk straight out of it into everything downstream, returning the source plus every component it reaches — one giant blob. Correct order, wrong graph. Reversing fixes exactly that. In `G^T`, every condensation edge flips too, so the source component of `G` becomes a **sink**: it has no outgoing cross-component edges in `G^T`. A traversal begun there can only travel inside the component. When it finishes, label everything it touched and move to the next unlabelled vertex in decreasing finish order. That vertex is in the next component in topological order, and every edge leaving it in `G^T` points back into components that are already labelled — so the traversal stops at the component boundary again. Induction does the rest. The reverse mistake — reversing the graph but visiting vertices in arbitrary order — fails for the mirror reason: start in the wrong place and one traversal on `G^T` merges several components. **Both ingredients are load-bearing.** That symmetry is the answer an interviewer is listening for. A by-product: components are emitted in topological order of the condensation, sources first. ## The one-pass contrast The low-link method (Tarjan's) reaches the same answer in a **single** traversal and without ever building a transpose. It assigns each vertex a discovery index and a *low-link* value — the smallest index reachable from that vertex's search subtree using tree edges plus at most one edge back to a vertex still on an auxiliary stack. Vertices are pushed onto that stack as they are discovered. When a vertex finishes with `low == index`, it is the root of a component, and everything above it on the stack is popped off as that component. Also O(V + E), it touches every edge once instead of twice, needs no reversed adjacency structure, and emits components in **reverse** topological order of the condensation. A path-based variant (Gabow's) achieves the same with two stacks and no low-link arithmetic. So the comparison is not asymptotic — both are linear. It is about constants and memory: two sweeps plus a full reversed edge list, versus one sweep plus three small per-vertex arrays and a stack. Kosaraju's advantage is that it is far easier to state, prove and get right by hand, which is exactly why it is the one interviewers ask you to explain. ## Things that go wrong - **Confusing finish time with discovery time.** Ordering by discovery time does not give a topological order of the condensation, and the algorithm breaks. - **Claiming two passes make it superlinear.** Two linear sweeps are still linear; the constant is what changes. - **Claiming the low-link method is asymptotically faster.** It is not — both are O(V + E). - **Skipping the transpose because "the order does the work".** Order alone leaks across component boundaries, as shown above.
- What breaks if you keep the decreasing finish order but forget to reverse the edges?The first traversal starts in a source component and walks straight out of it into everything downstream, returning that component plus all its descendants as one bogus group. The order picks the right starting point; the reversal is what stops the traversal from leaving the component.
- In what order does the two-pass method emit components, and how does the low-link method compare?The two-pass method emits them in topological order of the condensation, sources first, because it starts from the largest finish time. The low-link method emits them in reverse topological order, sinks first, as each component root finishes. Both run in O(V + E).
- Why is the total cost still O(V + E) despite two full traversals and a transpose?Each traversal touches every vertex and edge once, and building the reversed adjacency is a single scan of the edge list. Three linear phases sum to a linear total; only the constant factor, roughly three passes over the edges, differs from a one-pass method.
- What does the low-link value of a vertex actually mean?It is the smallest discovery index reachable from that vertex's search subtree using subtree edges plus at most one edge back to a vertex still on the algorithm's stack. When a vertex's low-link equals its own index, nothing in its subtree can escape above it, so it is the root of a component.
saying these in an interview costs you the question
- Says any traversal order works for the second pass
- Says reversing the edges alone is enough, order irrelevant
- Confuses finish time with discovery time
- Claims two traversals make the algorithm superlinear
- Believes the one-pass low-link method is asymptotically faster