Strongly connected components with Kosaraju in Python

Why it matters

A directed graph is a set of points joined by one-way arrows. A city with one-way streets is a directed graph. So is a set of software modules where one module imports another, or a list of tasks where one task must finish before another starts.

In a directed graph, some groups of points form loops. From any point in the loop you can follow the arrows and reach every other point in the loop. Other points are one-way: you can leave them but never come back. Finding the loop groups tells you which parts of a system are tangled together and which parts only depend on one direction.

This lesson teaches Kosaraju's algorithm. It finds those loop groups using only depth-first search, the walk that goes as deep as it can before backing up. The method runs the search twice: once on the graph as given, and once on a copy where every arrow points the other way. The earlier depth-first search lesson in this module covers the walk itself, so this lesson only shows how to use it.

Directed graphs and strong connection

Start with a small example. Three cities, A, B and C, have one-way roads: A to B, B to C, and C back to A. Leaving A you can reach B, then C, then A again. Every city can reach every other city. Mathematicians say these three cities are strongly connected, which means each one can reach each other one by following arrows.

Now change one road. Keep A to B and B to C, but remove C back to A. Leaving A you still reach B and C. But from C you cannot get back to A or B, because no arrow leaves C. The three cities are no longer strongly connected.

Here is the exact rule. Vertex a can reach vertex b if some path of arrows starts at a and ends at b. Two vertices are strongly connected if each can reach the other. A strongly connected component, shortened to SCC, is a largest group of vertices where every pair is strongly connected. "Largest" means you cannot add another vertex to the group and keep the property.

Every vertex belongs to exactly one SCC. A vertex with no loop through it forms an SCC on its own. In the broken example above, A, B and C are three separate SCCs, because no two of them can reach each other.

Two more terms are needed. A cycle is a path of arrows that starts and ends at the same vertex. A DAG, short for directed acyclic graph, is a directed graph with no cycles. A DAG is a graph where you can always order the vertices so that every arrow points forward in the order.

The condensed graph is made by squeezing each SCC into a single node. Arrows that stay inside one SCC disappear. Arrows between different SCCs stay, and they point between the squeezed nodes. The condensed graph is always a DAG. If it had a cycle, the SCCs on that cycle could all reach each other, and so they would have been one SCC to begin with.

The reversed graph

The second pass of Kosaraju's algorithm uses the reversed graph. It has the same vertices, and every arrow is flipped. An arrow from 1 to 2 becomes an arrow from 2 to 1.

Take the three-city loop again, with arrows A to B, B to C and C to A. The reversed graph has arrows B to A, C to B and A to C. It is still a loop, just traversed the other way.

Reversing the graph does not change its SCCs. Suppose a can reach b in the original graph. Then the path of arrows from a to b, read backwards, is a path from b to a in the reversed graph. So the two vertices are still strongly connected in the reversed graph. The same argument works in the other direction. The SCCs are the same in both graphs. The reversed graph is a tool, not a different answer.

The idea in two passes

Kosaraju's algorithm has two passes. Each pass is a depth-first search.

Pass 1 runs on the original graph. For each vertex, record the moment its call finishes. Call that moment the finish time. A call finishes when the search has explored everything it could reach from that vertex and returns. The vertex that finishes last in the whole pass is the one whose call returns last.

Pass 2 runs on the reversed graph. Go through the vertices in the opposite of finish order, starting with the one that finished last. If a vertex has not been labelled yet, start a depth-first walk from it on the reversed graph. Give every vertex that walk reaches the same new label. That label is one SCC.

The key fact is about the vertex that finishes last. Its SCC has no arrows coming in from any other SCC. In plain words, no other group of vertices points into it. Think about the three-city example with an extra city D that has an arrow into A. D is not in the loop, and the loop A, B, C has an arrow from D pointing into it. If the search starts in D, the loop finishes before D does. The group that feeds into others always finishes later than the group it feeds. So the last vertex to finish sits in a group that is fed by nothing.

Now run the second pass from that vertex on the reversed graph. Arrows that used to go into its group now leave it. The walk from the vertex can only reach vertices that could reach it in the original graph. Since nothing outside its group points into it, the walk stays inside its group. The walk labels exactly one SCC. Then the same argument applies to what is left, and the next unlabelled vertex in finish order is the start of the next walk.

The examples below make this concrete.

Worked example 1: one loop of three vertices

Use three vertices 0, 1 and 2 with arrows 0 to 1, 1 to 2, and 2 to 0.

Pass 1 starts at vertex 0. The walk goes 0, then 1, then 2. At vertex 2 the only arrow points back to 0, which the walk has already seen, so vertex 2 has nothing new to explore. Its call finishes first. Then vertex 1 finishes, then vertex 0. The finish order is 2, 1, 0.

Pass 2 goes through that list from the end, so it starts at 0. The reversed graph has arrows 1 to 0, 2 to 1 and 0 to 2. From 0 the walk goes to 2, then to 1. All three vertices get label 0. The loop is one SCC.

To check this in the program, set n = 3 and edges to [(0, 1), (1, 2), (2, 0)] in Program 1 below. It prints:

finish order: [2, 1, 0]
components: 1
component of each vertex: [0, 0, 0]
condensed edges:

The last line is empty because there are no arrows between different SCCs.

Worked example 2: two vertices and one arrow

Use two vertices 0 and 1, with one arrow from 0 to 1. There is no way to get from 1 back to 0, so the two vertices are not in a loop together. The answer should be two SCCs.

Pass 1 starts at 0 and goes to 1. Vertex 1 has no arrows out, so it finishes first. Then 0 finishes. The finish order is 1, 0.

Pass 2 starts with the last finished vertex, which is 0. The reversed graph has the single arrow 1 to 0, so there is no arrow leaving 0 in the reversed graph. The walk from 0 labels only vertex 0. Next comes vertex 1, which is not labelled yet. The walk from 1 follows the reversed arrow to 0, but 0 is already labelled, so the walk stops. Vertex 1 gets its own label.

Set n = 2 and edges to [(0, 1)] in Program 1. It prints:

finish order: [1, 0]
components: 2
component of each vertex: [0, 1]
condensed edges:
  0 -> 1

The condensed edge 0 -> 1 says the SCC labelled 0 has an arrow into the SCC labelled 1. That matches the original arrow.

Worked example 3: eight vertices with two loops

This graph has eight vertices, numbered 0 to 7. It has two loops, one on 0, 1 and 2, and one on 3, 4 and 5. It also has a loop on 6 and 7. The arrows between groups are 2 to 3 and 6 to 5. There are ten arrows in total.

Pass 1 starts at vertex 0 and walks 0, 1, 2, 3, 4, 5. At 5 the arrow back to 3 points to a vertex already on the walk, so 5 finishes first. Then 4 finishes, then 3. Back at 2, its other arrow to 0 is already seen, so 2 finishes. Then 1 and 0 finish. The search has not yet visited 6 or 7.

Pass 1 starts a new walk at 6, because it is still unseen. From 6 the arrow to 5 leads to a vertex already seen. The arrow to 7 leads to a new vertex. From 7 the arrow back to 6 is already seen, so 7 finishes first, then 6. The complete finish order is 5, 4, 3, 2, 1, 0, 7, 6.

Pass 2 processes the vertices from the end of that list, so it starts at 6. On the reversed graph, the walk from 6 follows the arrow from 7 back to 6, reaching 7. Vertex 7 has no other reversed arrows, so the walk labels 6 and 7 with label 0. This group has an arrow into the group of 3, 4 and 5, but nothing from 3, 4 and 5 goes back into 6 or 7, so the reversed walk does not leave the group.

Next the list gives 7, which is already labelled. Then 6, which is also labelled. Then 0. The walk from 0 on the reversed graph follows the arrow from 2 to 0, read backwards, to reach 2. From 2 it follows the arrow from 1 to 2, read backwards, to reach 1. From 1 it follows the arrow from 0 to 1, read backwards, back to 0. Those three vertices get label 1. The walk does not reach 3, because the only arrow from this loop into 3 is 2 to 3, and read backwards it goes from 3 to 2, which points into the loop, not out of it.

The last new walk starts at 3. The reversed walk from 3 reaches 5, then 4, and the arrow from 2 to 3, read in reverse, goes from 3 to 2. Vertex 2 is already labelled, so it is skipped. Vertices 3, 4 and 5 get label 2.

The labels are 0 for {6, 7}, 1 for {0, 1, 2} and 2 for {3, 4, 5}. Program 1 prints them in that order.

Program 1: Kosaraju's algorithm

Here is the full program. It stores the graph in two adjacency lists, one for the original arrows and one for the reversed arrows. An adjacency list is a list, for each vertex, of the vertices its arrows point to. In Python, each vertex's list is an ordinary list at that index, so adj[u] is the list for vertex u. It runs pass 1, then pass 2, then builds the condensed graph.

The two passes are plain functions. The adjacency lists are passed in as arguments, so the functions do not depend on global variables.

Save the file as kosaraju.py and run it with python3 kosaraju.py. The output was produced with Python 3.14.4:

finish order: [5, 4, 3, 2, 1, 0, 7, 6]
components: 3
component of each vertex: [1, 1, 1, 2, 2, 2, 0, 0]
condensed edges:
  0 -> 2
  1 -> 2

Three details in this output are worth a close look. First, the component numbers are handed out in the order the second pass finds them, not in sorted order. The group {6, 7} is component 0 because it was the first one found. Second, the condensed edges use those component numbers, so 0 -> 2 means the group {6, 7} has an arrow into the group {3, 4, 5}. Third, the condensed edges are kept in a set of pairs. A set stores each pair once and ignores repeats, so the program never needs a table with one cell for every pair of components. sorted puts the pairs in order before they are printed. For a very large graph, the set is the right choice, because most pairs of components have no arrow between them.

Printing a Python list shows it in square brackets with commas, so the output needs no helper function.

The program uses recursion, which means a function calls itself. Each call uses memory on the call stack, a region that holds one frame for each active call. Python limits how deep this stack can grow. The default limit is 1000 calls, and sys.getrecursionlimit() returns it. The section on common mistakes shows what happens when the recursion goes deeper than that.

Why the reversed walk stops at the group boundary

The argument in the idea section can be checked on the output. The last vertex in the finish list is 6. Its component is {6, 7}, with label 0. The arrows that cross between components are 2 to 3 and 6 to 5. Each goes from one group into another. None goes into {6, 7}, so nothing outside that group points back into it. When the second pass starts at 6 on the reversed graph, the walk cannot leave {6, 7}.

The same pattern holds at every step. After {6, 7} is labelled, the next unlabelled vertex in finish order is 0. The group {0, 1, 2} receives no arrow from {3, 4, 5}, so its reversed walk stays inside {0, 1, 2}. The arrow 2 to 3 leaves the group. In the reversed graph it becomes an arrow from 3 to 2, which points into the group, so a walk that starts in the group never follows it out. Reversing the arrows is what makes each walk stop at the right place.

Common mistakes

Forgetting to reverse the graph

The most common mistake is running pass 2 on the original graph. The code looks almost the same, with adj in place of radj in the call to second_pass. The result is wrong. Here is the output of that version on the same eight-vertex graph:

finish order: [5, 4, 3, 2, 1, 0, 7, 6]
components: 2
component of each vertex: [1, 1, 1, 0, 0, 0, 0, 0]

Only two components are reported, and the walk from 6 has swallowed {3, 4, 5}. On the original graph, 6 has an arrow to 5, so the forward walk from 6 goes into the loop on 3, 4 and 5. The walk does not stop at the group boundary, because the boundary is only visible when arrows point the right way.

Processing the finish list in the wrong order

Another mistake is to start pass 2 at the first vertex in the finish list, not the last. The correct order is the reverse of the finish list. Here is the output of a version that goes forward through the list on the reversed graph:

finish order: [5, 4, 3, 2, 1, 0, 7, 6]
components: 1
component of each vertex: [0, 0, 0, 0, 0, 0, 0, 0]

Everything is reported as one component. The first vertex in the list is 5, which sits in the middle of the graph. Its reversed walk reaches the whole graph, so it labels every vertex. The finish order must be used from the end, because the end is the group nothing points into.

Reading the finish order as the visit order

Pass 1 records vertices when their calls finish. It does not record when they are first seen. A beginner often adds the vertex to the list at the top of the function, where it is marked as seen. The list then holds the visit order, and pass 2 runs in the wrong order for the same reason as the mistake above. On the eight-vertex graph, that version gives this:

visit order: [0, 1, 2, 3, 4, 5, 6, 7]
components: 2
component of each vertex: [1, 1, 1, 1, 1, 1, 0, 0]

The fix is to put finish.append(u) after the loop over neighbours, as the program does.

Forgetting to skip labelled vertices

In pass 2 the check comp[v] == -1 stops the walk from entering a vertex that already has a label. If you remove that check, the walk does not stop on a loop of arrows. It goes around the loop again and again, until Python runs out of allowed calls. Here is the output of a run without the check on the eight-vertex graph, with the middle of the traceback left out:

...
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "...kosaraju_variants.py", line 77, in bad_second
    bad_second(v, radj, comp, label_id)
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

This output comes from a copy of Program 1 with that check removed, so the file names and line numbers differ from the program above. The last line is the error. The real problem is that the walk never ended, and the recursion limit is what stopped it.

Recursion that goes too deep

Both passes call themselves once per vertex on a path. A graph that is a single chain of many vertices makes the call stack very deep. A chain of 1500 vertices is already past the default limit of 1000. Running only pass 1 on that chain gives this:

Traceback (most recent call last):
  File "...kosaraju_check.py", line 46, in <module>
    first_pass(0, chain, [False] * m, [])
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "...kosaraju.py", line 5, in first_pass
    first_pass(v, adj, seen, finish)
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^
  File "...kosaraju.py", line 5, in first_pass
    first_pass(v, adj, seen, finish)
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^
  File "...kosaraju.py", line 5, in first_pass
    first_pass(v, adj, seen, finish)
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The last line names the error. The lines before it show the repeated calls to first_pass, with the line numbers of the code that made each call. The directory part of each path depends on where the files are saved.

Python can be told to allow more calls with sys.setrecursionlimit, but a higher limit only moves the failure to a longer chain, because each call still uses stack memory. For the graphs in a beginner course, recursion with the default limit is fine. For a production system with millions of vertices, you would write the walk with an explicit stack, which is a list that the program fills and empties itself, so the depth is limited by memory and not by the call limit.

Practice

Exercise 1 (easy). Find the SCCs of the directed graph with arrows 0 to 1, 1 to 2, 2 to 1 and 2 to 3. Hint: check which pairs can reach each other.

Show the answer

The SCCs are {0}, {1, 2} and {3}. Vertices 1 and 2 form a loop, so they are one SCC. Vertex 0 can reach the loop, but nothing in the loop reaches 0, so it is alone. Vertex 3 has no arrow back into the loop, so it is alone too.

Exercise 2 (easy). For the loop with arrows 0 to 1, 1 to 2 and 2 to 0, what is the finish order when pass 1 starts at vertex 1? Hint: start the walk at 1 and follow the arrows.

Show the answer

The finish order is 0, 2, 1. The walk goes 1, then 2, then 0. Vertex 0 has one arrow, to 1, which is already seen, so 0 finishes first. Then 2 finishes, then 1.

Exercise 3 (easy). Write out the reversed graph of the graph with arrows 0 to 1, 0 to 2 and 2 to 3.

Show the answer

The reversed graph has arrows 1 to 0, 2 to 0 and 3 to 2. Each original arrow is flipped, and nothing else changes.

Exercise 4 (medium). Explain why the condensed graph cannot contain a cycle. Hint: suppose two SCCs, A and B, each have an arrow into the other.

Show the answer

If A has an arrow into B and B has an arrow into A, then any vertex in A can reach any vertex in B, and back again. Every vertex in A can reach every vertex in B, and the reverse is also true. So A and B would be one SCC, not two. A cycle in the condensed graph would therefore mean the SCCs on it are really one SCC.

Exercise 5 (medium). Change Program 1 so that, after the components are found, it prints each component's vertices as a list, such as component 0: [6, 7]. Hint: create one list per component and add each vertex to the list for its label.

Show the answer

Add this code after the line that prints component of each vertex:

groups = [[] for _ in range(count)]
for v in range(n):
    groups[comp[v]].append(v)
for i in range(count):
    print(f"component {i}: {groups[i]}")

For the eight-vertex graph, the output is:

component 0: [6, 7]
component 1: [0, 1, 2]
component 2: [3, 4, 5]

The vertices are added in increasing order because the loop runs from 0 to n minus 1.

Summary

• A strongly connected component is a largest group of vertices where every vertex can reach every other one by following arrows.
• Kosaraju's algorithm runs depth-first search on the graph, records finish times, then runs depth-first search on the reversed graph in reverse finish order.
• Each walk in the second pass labels exactly one SCC, because the last-finished unlabelled vertex has no arrows coming in from other unlabelled groups.
• The condensed graph has one node per SCC and is always a DAG.
• The two most common mistakes are skipping the reversal and using the wrong order in the second pass.
• Both passes use recursion, so very deep graphs need an explicit stack.