Prove that contracting every strongly connected component of a directed graph yields an acyclic graph, and use that to justify the two-pass algorithm for finding the components in O(V + E). Why does the second pass use the reverse graph in decreasing finish time order?

Prove that contracting every strongly connected component of a directed graph yields an acyclic graph, and use that to justify the two-pass algorithm for finding the components in O(V + E). Why does the second pass use the reverse graph in decreasing finish time order?

Approach: Argue by contradiction on a cycle in the contracted graph, then use the property that the component finishing last in the first pass is a source of the condensation.

The condensation is acyclic, because a cycle through two distinct components would make every vertex on it mutually reachable and those components would then be one component, contradicting maximality. The two-pass algorithm uses that fact: run a depth first search on G recording finish times, then run a depth first search on the reverse graph taking roots in decreasing finish time, and each tree of the second pass is exactly one component. The vertex with the largest finish time lies in a source component of the condensation, since for any condensation edge from C to D the largest finish time in C exceeds the largest in D whichever of the two is entered first. Reversing the edges turns that source component into a sink, so a search from it reaches its own component and cannot spill into another. Deleting that component leaves the same property for the next unvisited vertex in finish order, so induction covers the graph. Both passes touch every vertex and edge a constant number of times, giving O(V + E).

Follow-up: How would you maintain the components incrementally as edges are added, and what is the best known amortised cost?

Key concepts: condensation, finish time, reverse graph, source component.