In a directed graph, being able to travel from one vertex to another does not imply that we can return. A dependency graph can contain tightly connected groups with one-way connections between them. Before reasoning about the order of those groups, we need to find exactly which vertices are mutually reachable.
Strongly connected components separate these two kinds of structure. Inside a component, every vertex can reach every other vertex. Between components, directed cycles disappear after contraction. The resulting graph is a directed acyclic graph, so an apparently cyclic dependency system can be studied as an acyclic arrangement of internally cyclic groups.
We will derive the two-pass DFS algorithm often called Kosaraju's algorithm. The first pass explores the original graph and records finishing order. The second pass explores the graph with every edge reversed, using the reverse of that order. Correctness depends on those exact choices; two arbitrary reachability searches do not suffice.
Mutual reachability defines the components
Let be a finite directed graph with vertices , where may be zero. Parallel arcs and self-loops are allowed. Write if there is a directed path from to , including a path of length zero when .
Definition 10.2.1
(Strong connectivity as an equivalence relation)
Define
A strongly connected component, or SCC, is an equivalence class for this relation. Equivalently, it is a maximal set of mutually reachable vertices. An isolated vertex forms a singleton component; it does not need a self-loop.
The relation is reflexive because of zero-length paths, and symmetric by its definition. If and , concatenate paths to obtain both and , proving transitivity. Thus the components partition all vertices rather than overlap.
Paths connecting vertices of one component can be taken entirely inside it. Indeed, if a vertex lies on a path from to and , then . Hence , so every intermediate vertex also belongs to that component.
The transpose graph contains for each arc in . Reversing a path reverses its reachability statement, so mutual reachability, and therefore the SCC partition, is unchanged by transposition.
Contracting components removes every directed cycle
Definition 10.2.2
(Condensation graph)
The condensation graph has one vertex per SCC and an arc when and an original edge goes from a vertex in to a vertex in . Internal edges are omitted; parallel arcs between the same two components need only one representative.
Theorem 10.2.3
(The condensation is acyclic)
The condensation graph of a finite directed graph is a directed acyclic graph.
Proof
(A cycle of components would merge them)
Suppose distinct component vertices formed a directed cycle. Using strong connectivity inside each component, we could follow that cycle to travel in both directions between any two of them. They would be one equivalence class, contradicting their distinctness. The condensation is therefore a DAG.
This does not say that the original graph is acyclic. It says that all directed cycles are contained inside its strong components. The condensation keeps the one-way relationships between those components.
The first DFS pass records returns, not discoveries
Run an ordinary directed DFS forest on , starting a new DFS at every still-unvisited vertex. Give each vertex a finishing time when its outgoing arcs have all been examined and all recursively discovered descendants have returned. It is enough to append the vertex to a list at that event; later list positions mean later finishing times.
For a component , let be the largest finishing time of a vertex in . Individual vertices of different components need not finish in separate contiguous blocks. The statement we need concerns these component maxima:
Theorem 10.2.4
(Finishing maxima decrease along condensation arcs)
Let be strongly connected components. If the condensation has an arc , then
Proof X-ray
A cross-component edge orders the largest finishing times
Consider which component, or , contains the first discovered vertex of their union.
If that vertex is in , its DFS can reach all of , cross the edge to , and reach all of . Paths inside the components suffice for this argument. All those still-undiscovered vertices are explored before this first vertex of finishes. It has the largest finishing time in , and it finishes after every vertex of , so .
If the first vertex is in , no path can lead from to , even through other components: together with , such a path would make the two components mutually reachable. The DFS beginning at that first vertex explores all of and finishes before any vertex of is discovered. Consequently every finishing time in precedes a finishing time in , again giving .
This lemma is stronger than saying that a DFS happened to visit one group first. It gives the direction of every inter-component dependency in terms of finishing maxima.
Common mistake
(Comparing single finishing times instead of component maxima)
Take arcs , , with neighbors tried in increasing order. The components are and , and the finishing order is . The arc leaves the first component, yet vertex 1 of that component finishes before vertex 2. Only the maxima compare correctly: the maximum finishing rank of is and that of is .
The second pass cannot escape its selected component
Scan vertices in decreasing finishing order. Whenever the next vertex is still unassigned, start a reachability search from it in , traversing only unassigned vertices. Assign all newly reached vertices to one component. A stack or queue is sufficient in this pass; there is no need to compute another finishing order.
Theorem 10.2.5
(Correctness of the two-pass algorithm)
Run a DFS on and record the finishing order. Then scan the vertices in decreasing finishing order; at each unassigned vertex, search in through unassigned vertices only and give everything reached a new ID. The searches assign exactly the strongly connected components of , and every arc between different components satisfies component[u] < component[v].
Proof X-ray
The next component is a source before transposition and a sink afterward
Inductively assume that every component selected earlier was assigned in full. The remaining components are therefore wholly unassigned. The first unassigned vertex in decreasing finishing order belongs to a component whose is maximal among the remaining components.
There cannot be an original edge from another remaining component into : the lemma would require . After transposition, there is therefore no edge from to a different unassigned component. Ignoring already assigned vertices, the search cannot leave .
All vertices of are nevertheless reachable from the selected vertex in , along paths lying entirely in . The search reaches every one of them. It assigns exactly , establishing the induction step. Repeating until no vertex remains gives precisely the SCC partition.
With this orientation of the two passes, components are produced in a source-to-sink topological order of the original condensation. If IDs are assigned as 0, 1, 2, and so on, every cross-component original edge satisfies component[u] < component[v]. This ordering claim is tied to using first and second; do not silently exchange the passes while keeping the same interpretation.
Counterexample mode
Discovery order and an unreversed graph both fail on one arc
Take only the edge . A DFS from 0 discovers vertices in order but finishes them in order . Reversing discovery order would start the second pass at 1 in the transpose. Since the transpose has , it would incorrectly merge both vertices.
The correct reverse finishing order is . But if we use it on the original graph rather than the transpose, the first search from 0 again reaches both vertices and incorrectly merges them. The actual components are and , because 1 cannot reach 0 in the original graph.
A complete trace, including an isolated component
Worked example 10.2.6
(An isolated vertex can precede a chain of components)
Use this adjacency list, with neighbor order as written and outer roots considered in increasing order:
| Vertex | Outgoing neighbors |
|---|---|
| 0 | 1 |
| 1 | 2, 3 |
| 2 | 0, 3 |
| 3 | 4 |
| 4 | 3, 5 |
| 5 | 6 |
| 6 | 5 |
| 7 | none |
The first DFS from 0 follows the chain of discoveries through 1, 2, 3, 4, 5, 6. Its returns append . Vertex 7 then supplies the final appended entry, so the complete finishing list is .
The second pass examines roots in order . It assigns components , , , in that order. Thus the ID array is . The two edges from the first nontrivial component to the next collapse to one condensation edge. Its edge set is , and component 0 remains as an isolated DAG vertex.
Counting finishing events from 1, the maxima are 7 for , 4 for , 2 for and 8 for . They decrease along every condensation edge; unrelated components need not have any particular relative order.
Worked example 10.2.7
(A directed cycle with a tail)
Take and arcs , , , . The DFS from 0 goes , then from 2 the arc to 0 meets a discovered vertex and the arc to 3 discovers 3. Returns append . The transpose has arcs , , , . The second pass scans roots . From 0 it reaches 2 and then 1, assigning to ID 0. The root 3 is next unassigned; its only transpose arc goes to the assigned vertex 2, so the search stops and assigns to ID 1. The ID array is , and the cross arc satisfies . The condensation has one edge .
Preserve DFS return events with explicit frames
A plain stack used for reachability need not reproduce recursive DFS finishing events. In the first pass, a frame must remember which outgoing arc to inspect next. When that frame has exhausted its adjacency list, append its vertex to the finishing list and pop it. Before descending to a new child, advance the parent's remembered index so that returning resumes at the next arc.
Mark a vertex when it is pushed, rather than waiting until it is popped. This prevents repeated arcs, cycles and self-loops from pushing the same undiscovered vertex multiple times. The second pass only needs reachability, so its stack can store vertices without return indices.
The input below is an indexable sequence of adjacency sequences, with integer neighbor labels. Invalid neighbor indices are rejected, including negative indices, which Python would otherwise interpret as indexing from the end. The input is read without mutation. The function returns an ID per vertex and one membership list per component; member order and the relative IDs of unrelated components are not canonical.
def strongly_connected_components(graph):
n = len(graph)
transpose = [[] for _ in range(n)]
for vertex, neighbors in enumerate(graph):
for neighbor in neighbors:
if not 0 <= neighbor < n:
raise ValueError("neighbor outside the vertex range")
transpose[neighbor].append(vertex)
seen = [False] * n
finish = []
for root in range(n):
if seen[root]:
continue
seen[root] = True
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index == len(graph[vertex]):
stack.pop()
finish.append(vertex)
continue
neighbor = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if not seen[neighbor]:
seen[neighbor] = True
stack.append((neighbor, 0))
component = [-1] * n
groups = []
for root in reversed(finish):
if component[root] != -1:
continue
identifier = len(groups)
component[root] = identifier
stack = [root]
members = []
while stack:
vertex = stack.pop()
members.append(vertex)
for neighbor in transpose[vertex]:
if component[neighbor] == -1:
component[neighbor] = identifier
stack.append(neighbor)
groups.append(members)
return component, groups
def condensation_edges(graph, component):
return sorted({
(component[u], component[v])
for u, neighbors in enumerate(graph)
for v in neighbors
if component[u] != component[v]
})
Call condensation_edges with the IDs returned for that same graph. The DAG has len(groups) vertices, even if some have no incident edges and hence do not occur in the returned edge list. The set removes duplicate cross-component arcs, and sorting makes the returned pair list easy to inspect; it is not needed for the SCC proof.
For an empty graph, both loops are empty and the result is ([], []). A self-loop only meets an already marked vertex; repeated arcs can repeat an edge examination but do not change reachability. There is no recursion-depth dependence.
Worked example 10.2.8
(Membership order is different from the mathematical component set)
For the eight-vertex example, the code returns groups . The middle order follows the transpose search, while the mathematical component is the set . Sorting that membership list for display would not change the partition.
If we add another copy of or add a self-loop at 7, no SCC changes. The sorted condensation edge list remains for this traversal. Its isolated vertex 0 still represents even though 0 does not occur in any edge pair.
Complexity and the meaning of the output
Let count all listed arcs, including duplicates. Building the transpose takes time and storage. In each pass every vertex is pushed at most once and each listed arc is examined at most once; the explicit first-pass frames resume instead of restarting an adjacency scan. Consequently finding the components takes time and additional cells, including the transpose, stacks and output.
The optional sorted edge helper has a separate cost. If is the number of distinct cross-component pairs, scanning the adjacency lists and creating the set takes expected time with hash-set operations, then sorting takes comparisons and needs additional cells. Do not describe the sorted-helper output as part of an unconditional linear-time bound. These are ordinary graph-operation/cell bounds, not bit-complexity bounds for arbitrarily large labels.
Counterexample mode
A smaller component ID does not prove reachability
In the example, isolated component receives ID 0 and component receives ID 1. There is no path from the former to the latter. Topological order guarantees that an existing cross-component path moves toward larger IDs; it does not guarantee that every smaller ID can reach every larger one.
Likewise, changing root or neighbor order may change IDs without changing the SCC partition. Compare partitions by mutual membership, not by expecting one universal numeric label for each component.
The condensation is useful for subsequent dependency processing, but an SCC is not automatically one cost-free vertex for every optimization problem. If a later problem asks for path lengths, capacities or visit constraints inside a component, those internal details need a separate argument. The partition proves mutual reachability; it does not erase every other feature of the original graph.
Common mistake
(Using the condensation for distances inside a component)
Contracting the directed cycle to one vertex discards that the shortest path from to has two arcs. The condensation records only which components can reach which; path lengths, capacities and visit constraints inside a component need their own argument.
Exercises with complete solutions
Quick check
(1. Why does an isolated vertex form an SCC without a self-loop? Show why mutual reachability is transitive, so two SCCs cannot overlap.)
Solution · 1. Zero-length paths and concatenation establish the partition
The zero-length path makes every vertex reachable from itself, including an isolated one. If and , concatenate and to obtain . Along with reflexivity and symmetry this is an equivalence relation, whose classes are disjoint. Overlapping mutually reachable maximal sets would therefore have to be one class.
Quick check
(2. In the eight-vertex example, what are the finishing maxima of {0,1,2}, {3,4} and {5,6}? Why can {7} receive the first component ID without contradicting the ordering lemma?)
Solution · 2. Finishing maxima constrain edges, not unrelated components
Their maxima are 7, 4 and 2, respectively, using one-based finishing ranks. The condensation edges follow . Vertex 7 finishes at rank 8 and its singleton is selected first. It has no edges connecting it to the others, so the lemma places no relative constraint between that component and the chain.
Quick check
(3. For the single arc , give discovery order, finishing order and correct second-pass root order. Explain separately what goes wrong with reverse discovery order or with no transposition.)
Solution · 3. Both finishing and reversing edges are necessary
Discovery order is , finishing order is , and the correct second-pass root order is on the transpose. Reversed discovery starts from 1 there and reaches 0, falsely merging them. Correct root order on the original graph starts at 0 and reaches 1, also falsely merging them. Correct order on the transpose assigns the two singleton SCCs separately.
Quick check
(4. Can adding a duplicate arc or a self-loop change the SCC partition? Why does marking on push matter for the implementation even though such arcs do not change reachability?)
Solution · 4. Edge multiplicity does not create new reachable pairs
A duplicate arc offers a step already available; a self-loop can be removed from any walk without changing its endpoints. Neither adds a new pair of distinct mutually reachable vertices. Marking on push ensures later examinations see the vertex as discovered immediately, preventing repeated pushes through duplicate arcs or cycles. The same reachability facts must still be implemented with controlled stack work.
Quick check
(5. Why does the eight-vertex condensation contain only (1,2) and (2,3), although two original arcs enter vertex 3 from component 1? How many DAG vertices does it have?)
Solution · 5. Deduplicate edges without dropping isolated vertices
Both and induce the same component pair , so only one representative is needed. Edge induces ; all other listed edges stay inside components. There are four DAG vertices, one per group. The isolated ID 0 is retained through the vertex count, even though it does not appear in any edge pair.
Quick check
(6. If component[u] is smaller than component[v], must u reach v? What direction of implication is justified by the output ordering?)
Solution · 6. Topological labels constrain paths without asserting that paths exist
No: in the example vertex 7 has a smaller component ID than vertex 0, but cannot reach it. What holds is that if reaches and their components differ, the condensation path has one or more cross-component edges, each increasing the ID, so component[u] < component[v]. If both vertices are in the same component, they are mutually reachable and their IDs are equal.