Motivation
In a directed graph, reachability in one direction need not imply reachability back. A strongly connected component groups vertices that can reach one another, and contracting these groups reveals an acyclic structure. The two-pass algorithm uses depth-first finishing times to choose components in an order that makes each component isolated from the remaining search in the transposed graph.
The proof depends on whole components and their maximum finishing times, not on every vertex of one component finishing after every vertex of another. Keeping that distinction visible avoids a common error in the ordering argument.
Definitions
Definition 3.5.1
(Strongly connected component and condensation graph)
Let be a finite directed graph. Vertices are strongly connected if each can reach the other by a directed path; paths of length zero are allowed. A strongly connected component (SCC) is an equivalence class of this relation. The condensation graph has one vertex per SCC and an edge when and an original edge goes from a vertex in to a vertex in .
Definition 3.5.2
(Transpose and component finishing time)
The transpose reverses every edge. Run a complete depth-first search (DFS) of , restarting from any unvisited vertex until all vertices are visited, and record the finishing time of each vertex. For an SCC , let be the maximum finishing time among the vertices of .
The two-pass procedure processes vertices in decreasing finishing-time order; whenever an unassigned vertex is encountered, it starts a DFS from that vertex in , ignoring already assigned vertices. The vertices found by that search form one output group.
Theorems
Theorem 3.5.3
(Condensation and finishing times)
The condensation graph is acyclic. If it has an edge , then a complete DFS of satisfies .
Theorem 3.5.4
(Two-pass SCC algorithm)
The output groups of the two-pass procedure are exactly the SCCs of . With adjacency lists, both passes and transpose construction take time and space.
Proof sketch or proof idea
The first proof covers both claims of the first theorem.
Proof
(Acyclic condensation and finishing times along an edge)
Mutual reachability is reflexive and symmetric by definition and transitive by concatenating paths, so its equivalence classes partition the vertices. If distinct components formed a directed cycle in the condensation graph, paths along that cycle together with paths inside components would make all vertices on the cycle mutually reachable. They would be one component, a contradiction. Thus the condensation graph is a DAG.
For an edge , compare the first discovery of any vertex in . Suppose the first discovered vertex lies in . At that moment every other vertex of is undiscovered. A path inside leads from to the tail of the edge, the edge enters , and paths inside reach every vertex of ; all of these vertices are still undiscovered. DFS therefore explores every one of them before it returns from , so finishes after every vertex of , and . Suppose instead the first discovered vertex lies in . No path leads from to : such a path together with would merge the two components. DFS from therefore reaches every vertex of and finishes all of them before discovering any vertex of . Every vertex of is discovered, hence finishes, after every vertex of , and again .
The second proof covers the two-pass algorithm. It is an induction over the second-pass searches.
Proof
(Each second-pass search outputs exactly one component)
Invariant: before each second-pass search, the assigned vertices form a union of whole SCCs, and each emitted group is one of them. Initially nothing is assigned.
Let be the unassigned vertex of largest finishing time and its SCC. All vertices of are unassigned, and finishing times are distinct, so exceeds for every other remaining component . If a remaining had an edge in the condensation, the first theorem would give , which is impossible. So is a source among the remaining components. In , every edge that leaves therefore ends in or at an assigned vertex. Because the search ignores assigned vertices, it never leaves . Conversely, any two vertices of are mutually reachable in by paths that stay in (reversing a path inside gives a path inside ), and all of is unassigned, so the search from reaches every vertex of . The emitted group is exactly , and the invariant is preserved. Every vertex is eventually assigned, so the groups are exactly the SCCs.
Building the transpose and each complete DFS scan each vertex and edge a constant number of times with adjacency lists. Reversing finishing order can be done with a stack or list, so total time and additional space are .
Proof X-ray
Where the second pass could escape
The first theorem is used exactly once in the second proof: to exclude a remaining component with an edge into the chosen component . That is also why maxima suffice. The vertex with the largest finishing time is by itself the maximum of its component, so no statement about other individual vertices is needed.
The non-obvious move is the reversal of edges. In , the component may well have edges leaving it toward other remaining components, and a search would follow them; the finishing-time theorem only guarantees that no remaining component has an edge into . Reversing every edge turns exactly this guarantee into the statement that nothing leaves . Two hypotheses carry weight. The search must skip assigned vertices, because original edges from earlier-assigned components into become edges out of in . The start vertices must come from the first-pass finishing order, because only that order is tied to the condensation edges by the theorem. The argument closes by induction: removing a whole component leaves remaining components that are still ordered by , so the same choice is available at the next step.
Worked examples
Worked example 3.5.5
(Three components in a chain, with finishing times)
Let the edges be , , , , and , and scan adjacency lists alphabetically. Start the first DFS at . It discovers , then and (the edge leads to an already discovered vertex and the edge likewise), and finally . Discovery times are for . Then finishes at time , at , at , at and at . So , and : the maxima decrease along the chain , as the theorem predicts.
The transpose has edges , , , , and . Decreasing finishing order is . The search from reaches only : group . Vertex is skipped. The search from sees the edge to , which is assigned and ignored, and reaches : group . Vertex is skipped. The search from ignores its edge to the assigned vertex : group . The three groups are the SCCs.
Worked example 3.5.6
(A one-way edge)
For two vertices with no return path, the SCCs are and . Reachability from to alone does not make them one component. The condensation graph has a single edge .
Worked example 3.5.7
(A cycle is one component)
In the directed cycle , each vertex can reach the other two. All three belong to one SCC, even though no pair of vertices has a direct edge in both directions.
Common mistakes
Counterexample mode
An edge does not imply mutual reachability
The graph has a path from to but none back. Treating directed reachability as an undirected relation merges two distinct components.
Common mistake
(Comparing individual finishing times instead of maxima)
The theorem compares and , the maximum finishing times, when the condensation has an edge . It does not claim that every vertex of finishes after every vertex of . In the example below, and with can produce the finishing order , so finishes before although .
Common mistake
(Dropping the assigned-vertex bookkeeping in the second pass)
The second pass must ignore vertices assigned by previous searches, and it must start its searches in the decreasing finishing order of the first pass. Computing a fresh finishing order during the second pass, or letting a search re-enter assigned vertices, breaks the argument that each search stays inside one component.
Why finishing-time maxima suffice
Depth-first search assigns a discovery time when it first visits a vertex and a finishing time after it has examined all outgoing edges and returned from recursive descendants. Finishing times are distinct in the usual sequential implementation. A DFS tree can contain vertices from several SCCs; the theorem does not require each component to be a contiguous subtree of the complete DFS forest.
Consider an edge from component to a distinct component . If a vertex of is discovered first among the two components, every vertex of and is still undiscovered at that instant except that starting vertex. Paths inside , the edge to , and paths inside show that the first vertex can reach every vertex of through vertices not yet visited in those components. DFS finishes all of those descendants before returning from the first vertex. Its finishing time is therefore larger than the finishing time of every vertex in , which implies the maximum inequality.
If a vertex of is discovered first, the existence of rules out any path from back to . A DFS started at that first vertex reaches all of but cannot discover a vertex of before it finishes. Every vertex therefore finishes before the first discovery. These two cases establish the same comparison without assuming which component DFS visits first.
Worked example 3.5.8
(A finishing order need not group vertices)
Let with edges both ways, let , and add . Start DFS at and explore before . The finishing order can be . The component is interleaved with in that order, but is the finishing time of , which is greater than . The theorem concerns maxima, not a contiguous block of individual times.
Why the second pass extracts a whole component
Reversing all edges reverses every path, so vertices mutually reachable in remain mutually reachable in . The SCC partition is unchanged, while every edge of the condensation graph reverses direction. At the start of each second-pass search, assume previously output groups were whole components; this is the induction hypothesis.
The unassigned vertex with the largest finishing time belongs to a component whose maximum is largest among remaining components. If another remaining component had an edge into it in the original condensation, the finishing-time theorem would give that predecessor a larger maximum. This is impossible. The chosen component is therefore a source among the remaining components. In the transpose it has no edge to another remaining component. A search that refuses to enter assigned vertices cannot leave the chosen component, while mutual reachability in the transpose ensures that it reaches every vertex of that component. The resulting group is exactly one SCC, preserving the induction hypothesis.
Edges from an unassigned component to an already assigned one in the transpose do not invalidate this reasoning because the search explicitly ignores assigned vertices. An implementation that starts a new DFS without tracking prior assignments could repeatedly traverse vertices already output and would not directly implement the stated proof. The order is decreasing finishing time from the first graph, not a fresh finishing order computed during the second pass.
Counterexample mode
Searching the original graph in the second pass
Suppose the second pass searched itself, in decreasing finishing order, instead of . Take with the single edge . Every complete DFS finishes before (started at , it finishes and then ; started at , it finishes first and only then discovers ). Decreasing order therefore begins with , and a search of from reaches , so the output is the single group . But there is no path from back to , so the SCCs are and . In , whose only edge is , the search from finds only and the next search finds . The repair is the transpose: the first vertex in the order lies in a source component, which has no outgoing edge to another remaining component only after the edges are reversed.
An implementable trace
A first DFS can append each vertex to a list when it finishes. Reading the list backward gives decreasing finishing time; no numerical timestamps are necessary. Construct by adding edge for each original edge . Initialize every vertex as unassigned. Scan the reversed finish list; if a vertex is already assigned, skip it. Otherwise run a graph search in , mark each discovered vertex with the current component identifier, and emit that group when the search finishes.
The second pass may use DFS or another exhaustive graph search: the proof needs it to visit exactly the unassigned vertices reachable from its start in the transpose. The first pass specifically needs DFS finishing times. Adjacency lists make each directed edge available in constant time per traversal. Transpose construction, both graph searches and the final scan together inspect entries. A dense adjacency matrix has a different scanning cost, so the representation is part of the stated complexity.
The output groups can be used to build a condensation graph by scanning original edges and adding an edge whenever their endpoint identifiers differ. Parallel edges between the same two components may be retained or deduplicated according to the desired representation; either choice has the same reachability structure. An SCC algorithm does not automatically output a particular topological ordering unless its convention and order are specified.
Checking a proposed partition
To verify a claimed component, one can select a representative and check reachability from it to every vertex in the group and from every vertex back to it, using only vertices in the group. Reversing edges turns the second collection of checks into another search from the representative. If every group is internally strongly connected and the graph obtained by contracting groups is acyclic, the groups are the SCCs: a larger mutual-reachability class would create a cycle among distinct contracted groups.
This certificate separates internal connectivity from maximality. Merely showing that each proposed group is strongly connected is insufficient: splitting a directed cycle into singleton groups satisfies that local condition but fails maximality. Conversely, an acyclic graph of arbitrary groups is insufficient if a group itself contains vertices that cannot reach one another. Both parts are needed.
A graph with no edges has one SCC per vertex, including isolated vertices. An empty graph has no components. A self-loop does not merge its vertex with another component. These cases follow from the same definitions and do not require a special exception in the two-pass procedure.
Summary
Mutual reachability partitions a directed graph into SCCs, whose condensation is a DAG. DFS finishing-time maxima decrease along condensation edges. Processing the transpose in decreasing finish order extracts one remaining source component at a time.
Exercises
Quick check
(What are the SCCs of the graph with vertices and the single edge ?)
Ask whether can reach .
Solution · Answer
They are and , because cannot reach .
Quick check
(Why can the condensation graph not contain a directed cycle?)
Combine the paths along the cycle with paths inside components.
Solution · Answer
A cycle would provide paths in both directions between any two of its components, so all vertices on the cycle would be mutually reachable and the components would not be distinct.
Quick check
(If the condensation has an edge , which component has the larger maximum finishing time?)
Recall the finishing-time theorem.
Solution · Answer
The component , the tail of the edge: .
Quick check
(Why does transposing preserve the SCC partition?)
What happens to a path when every edge is reversed?
Solution · Answer
Reversing every edge reverses every path. Mutual reachability holds in the transpose exactly when it holds in the original graph.
Exercise 3.5.9
(Run the two-pass algorithm on the graph with vertices and edges , , , , , , scanning adjacency lists in increasing order, and list the output groups.)
Core
Hint(1)
Record the order in which vertices finish; the numerical times are not needed.
Solution(4)
- 1
Run the first DFS from vertex 1
The search discovers ; the edge returns to a discovered vertex, so it continues to and , where the edge is likewise skipped. Vertices finish in the order .
- 2
Transpose the graph and reverse the finishing order
The transpose has edges , , , , , . Decreasing finishing order is .
- 3
Search the transpose, skipping assigned vertices
Key step
From the search reaches and then , giving the group ; vertices and are then skipped. From the edge to is ignored because is assigned, and the search reaches : group .
Because: A search in the transpose from the vertex of largest finishing time cannot leave its component.
- 4
State the groups and check them
The output is and . These are the SCCs: and are cycles, and the only edge between them is . This agrees with the theorem, since vertex finishes last (time ) while the maximum in is smaller (time ).