Why it matters
A directed graph has arrows that go one way. A web page links to another page, but that page may not link back. A course has prerequisites that point from one course to the next. A build tool has modules that import other modules, and each import is one arrow.
Two questions come up again and again with such graphs. Which vertices can reach each other in both directions? And if you squash each such group into one box, what does the graph look like between the boxes? A package manager asks the first question to find modules that depend on each other in a loop. A crawler asks it to find sets of pages that all link into each other. Both questions have the same answer: the strongly connected components.
This lesson is about directed graphs. It assumes you know how to store a graph as a list of neighbours and how a depth-first search (DFS) walks it. DFS goes as deep as it can before it backs up. If that idea is new to you, read the DFS lesson earlier in this module first.
Words you need
A directed graph is a set of vertices (points) and a set of edges (arrows). An edge u -> v lets you walk from u to v, but not back, unless there is another edge that does.
A vertex v is reachable from u if you can follow arrows from u and arrive at v. A vertex always reaches itself, because you can walk zero steps.
A strongly connected component, usually shortened to SCC, is a largest set of vertices where every vertex can reach every other vertex in the set. Largest means you cannot add another vertex without breaking that rule.
The reversed graph is the same graph with every arrow turned around. The edge u -> v becomes v -> u. Reversing the graph does not change which vertices form a component, but it changes which vertices can reach which, and that is the property the algorithm uses.
The finish order is the order in which a DFS finishes each vertex. A vertex finishes when the DFS has tried every arrow leaving it. If you write the vertices down in finish order, the last one written is the one that finished last.
The condensed graph is what you get when you replace each SCC with a single box. Two boxes get an arrow when some original edge goes from a vertex in the first box to a vertex in the second. The condensed graph never has a loop, because two SCCs that could reach each other would be one SCC. A graph with no loops in this sense is called a directed acyclic graph, or DAG.
A small example first
Take three vertices and three arrows: 0 -> 1, 1 -> 2, and 2 -> 0. You can walk 0 -> 1 -> 2 -> 0, so each vertex reaches the others. All three form one SCC.
Now add a fourth vertex and one arrow, 2 -> 3. Vertex 3 has no arrow back to the cycle, so it cannot reach 0, 1 or 2. It forms an SCC of its own. The condensed graph has two boxes: {0, 1, 2} and {3}, with one arrow from the first box to the second.
The rest of the lesson uses this idea on bigger graphs. The question for the algorithm is simple to state: given any graph, which vertices belong in the same box?
The idea behind Kosaraju's algorithm
Kosaraju's algorithm uses two depth-first searches. It was described by S. Rao Kosaraju. The first search only records an order. The second search, run on the reversed graph, collects the boxes.
Here is why the order helps. Suppose a DFS starts at a vertex v that belongs to some SCC C. Every vertex in C is reachable from v, and v is reachable from every vertex in C. When the DFS from v finishes, every vertex it reached has finished. That includes all of C, but it may also include vertices in other SCCs that C can reach. Those other SCCs will finish first, because they are reached from inside C and finish before the DFS returns to C.
So the finish order has a useful property. The vertex that finishes last belongs to an SCC with no arrows coming into it from outside. If we start a search from that vertex on the reversed graph, the search cannot leak out of its own SCC. In the reversed graph, the arrows into the SCC have become arrows out of it, and those arrows lead to SCCs that were already processed or that cannot reach back.
That is the whole idea. Pass 1 gives an order. Pass 2 walks the reversed graph in that order, and each walk collects exactly one SCC.
The two passes step by step
Pass 1: record the finish order
Run a DFS on the original graph. Start from every vertex that has not been seen yet. When a vertex's DFS call is done, which means all of its neighbours have been handled, write the vertex into a list. That list is the finish order.
Mark each vertex as seen when you enter it. Skip any neighbour that is already seen. Without the seen marks, the search would walk around loops forever.
Pass 2: walk the reversed graph
Build the reversed graph. Then go through the finish order from the last entry to the first. For each vertex that is not yet part of a component, run a DFS on the reversed graph starting from that vertex. Every vertex that DFS reaches and has not been placed yet becomes one new component. Give that component the next number.
Each walk only collects vertices that are not yet placed, so the walks never mix two SCCs. When the walks are done, every vertex has a component number.
Worked example: an eight-vertex graph
The next example has two cycles joined by an arrow, and a third part that is a cycle of two vertices. The arrows are:
0 -> 1, 1 -> 2, 2 -> 0
2 -> 3
3 -> 4, 4 -> 5, 5 -> 3
5 -> 6
6 -> 7, 7 -> 6Before reading further, try to guess the SCCs. The answer should be {0, 1, 2}, {3, 4, 5} and {6, 7}. The arrow 2 -> 3 joins the first and second groups, and 5 -> 6 joins the second and third, but there is no arrow back, so the groups stay separate.
Here is the pass 1 trace, written out. Start the DFS at vertex 0. The walk goes 0, then 1, then 2. From 2, the neighbour 0 is already seen, so skip it. The next neighbour is 3, so the walk goes to 3, then 4, then 5. From 5, the neighbour 3 is seen. The next neighbour is 6, so the walk goes to 6, then 7. From 7, the neighbour 6 is seen, so 7 finishes. Then 6 finishes, 5 finishes, 4, 3, 2, 1 and 0 finish in that order.
The finish order is 7, 6, 5, 4, 3, 2, 1, 0. Every vertex has been seen now, so the outer loop starts no new searches.
Pass 2 uses the reversed graph and reads the finish order from the last entry to the first. The last entry is 0. A walk on the reversed graph from 0 reaches 2 (because the original arrow was 2 -> 0), then 1, and then 0 again, which is already placed. The first component is {0, 1, 2}.
The next entry in the reversed order is 1, which is already placed, so skip it. Then 2, also placed. Then 3. A walk from 3 on the reversed graph follows the arrows that point into 3 in the original graph. Those are 2 -> 3 and 5 -> 3. Vertex 2 is already placed, so the walk takes 5, then 4 (because the original arrow was 4 -> 5), then 3, which is the start. The second component is {3, 4, 5}.
The next unplaced entry is 6. A walk from 6 on the reversed graph reaches 5, which is placed, and 7, which is new. The third component is {6, 7}.
The program below does exactly these steps and prints the results. Its output matches the trace.
The program
This program uses std::vector for the graph, std::size_t for vertex numbers, and two small recursive functions for the two passes. It prints the finish order, the components, and the arrows of the condensed graph.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using Vertex = std::size_t;
using Graph = std::vector<std::vector<Vertex>>;
Graph reversed(const Graph& g) {
Graph r(g.size());
for (Vertex u = 0; u < g.size(); ++u) {
for (Vertex v : g[u]) {
r[v].push_back(u);
}
}
return r;
}
// Pass 1: record each vertex after all of its neighbours are finished.
void first_pass(const Graph& g, Vertex v, std::vector<bool>& seen, std::vector<Vertex>& finish_order) {
seen[v] = true;
for (Vertex next : g[v]) {
if (!seen[next]) {
first_pass(g, next, seen, finish_order);
}
}
finish_order.push_back(v);
}
// Pass 2: on the reversed graph, everything reached belongs to one component.
void second_pass(const Graph& r, Vertex v, std::vector<int>& component, int id) {
component[v] = id;
for (Vertex next : r[v]) {
if (component[next] == -1) {
second_pass(r, next, component, id);
}
}
}
void print_list(const std::vector<Vertex>& items) {
std::cout << "[";
for (std::size_t i = 0; i < items.size(); ++i) {
std::cout << items[i] << (i + 1 < items.size() ? ", " : "");
}
std::cout << "]";
}
int main() {
const Vertex n = 8;
const std::vector<std::pair<Vertex, Vertex>> edges = {
{0, 1}, {1, 2}, {2, 0}, {2, 3},
{3, 4}, {4, 5}, {5, 3}, {5, 6},
{6, 7}, {7, 6},
};
Graph g(n);
for (auto [u, v] : edges) {
g[u].push_back(v);
}
std::vector<bool> seen(n, false);
std::vector<Vertex> finish_order;
for (Vertex v = 0; v < n; ++v) {
if (!seen[v]) {
first_pass(g, v, seen, finish_order);
}
}
std::cout << "finish order: ";
print_list(finish_order);
std::cout << "\n";
const Graph r = reversed(g);
std::vector<int> component(n, -1);
int count = 0;
for (auto it = finish_order.rbegin(); it != finish_order.rend(); ++it) {
if (component[*it] == -1) {
second_pass(r, *it, component, count);
++count;
}
}
for (int id = 0; id < count; ++id) {
std::vector<Vertex> members;
for (Vertex v = 0; v < n; ++v) {
if (component[v] == id) {
members.push_back(v);
}
}
std::cout << "component " << id << ": ";
print_list(members);
std::cout << "\n";
}
std::set<std::pair<int, int>> condensed;
for (Vertex u = 0; u < n; ++u) {
for (Vertex v : g[u]) {
if (component[u] != component[v]) {
condensed.insert({component[u], component[v]});
}
}
}
std::cout << "condensed edges:";
for (auto [a, b] : condensed) {
std::cout << " " << a << "->" << b;
}
std::cout << "\n";
}Compile and run it with the warning flags turned on:
g++ -std=c++20 -Wall -o scc scc.cpp && ./sccThe output is:
finish order: [7, 6, 5, 4, 3, 2, 1, 0]
component 0: [0, 1, 2]
component 1: [3, 4, 5]
component 2: [6, 7]
condensed edges: 0->1 1->2The component numbers come out in an order that matters. Component 0 has no arrows coming in from the other components, component 1 only receives arrows from component 0, and component 2 only receives from component 1. Kosaraju's algorithm always numbers components so that each arrow in the condensed graph goes from a lower number to a higher number. That makes the condensed graph easy to process in order.
Why both passes need to be there
The two passes do different jobs, and swapping either one breaks the result. Two wrong versions show why. Both run on the same graph, with the same program except for one line.
The first wrong version takes the finish order and reads it from the first entry to the last, instead of from the last to the first. The first entry is 7. A walk on the reversed graph from 7 follows arrows into 7, then into 6, then into 5, 4, 3, 2, 1 and 0, because they all lead to 7 through the cycle. The walk collects everything into one component:
finish order: [7, 6, 5, 4, 3, 2, 1, 0]
component 0: [0, 1, 2, 3, 4, 5, 6, 7]
condensed edges:The second wrong version walks the original graph instead of the reversed one, in the same finish order. Starting at 0, a walk on the original graph goes all the way to 7, because every vertex is reachable from 0. It also collects everything:
finish order: [7, 6, 5, 4, 3, 2, 1, 0]
component 0: [0, 1, 2, 3, 4, 5, 6, 7]
condensed edges:Both wrong versions give one big component, which is not what the graph looks like. The reversed graph and the reading order from last to first are the two things that keep each walk inside one SCC.
The condensed graph
After pass 2, the component numbers tell you which box each vertex is in. To build the condensed graph, look at every original arrow u -> v. If u and v are in different components, record an arrow from u's component to v's component. Remove duplicates, because many original arrows may connect the same two boxes.
In the eight-vertex example, the arrows that cross between boxes are 2 -> 3 (from component 0 to component 1) and 5 -> 6 (from component 1 to component 2). The condensed graph has the two arrows 0 -> 1 and 1 -> 2. There are no other crossing arrows.
The condensed graph is always a DAG. Suppose it had a cycle, with boxes A and B pointing at each other. Then a vertex in A could reach a vertex in B, and that vertex could reach back to A. Those vertices would be in the same SCC, so A and B would be one box. That contradicts the assumption. So the condensed graph has no cycles, and you can run a topological sort on it.
This is useful in practice. If the boxes are modules, the condensed graph tells you the order in which to build the groups. Each group needs only the groups before it. A cycle inside one group still has to be handled as a unit, but the groups themselves can be ordered.
A harder example: the same vertices, a different shape
Example 2 uses the same algorithm on a graph where the first DFS starts in the middle of a cycle. The graph has four vertices and these arrows: 0 -> 1, 1 -> 0, 1 -> 2, 2 -> 3 and 3 -> 2.
Pass 1 starts at 0, goes to 1, and from 1 goes to 0 (already seen) and then to 2. From 2 the walk goes to 3. Vertex 3 has neighbour 2, already seen, so 3 finishes. Then 2, 1 and 0 finish. The finish order is 3, 2, 1, 0.
Pass 2 reads the order from the last entry. Vertex 0 gives a reversed walk that reaches 1 (because 1 -> 0 in the original), and then stops, because 2 is not reachable from 0 on the reversed graph. The first component is {0, 1}. Vertex 1 is placed, vertex 2 gives a reversed walk that reaches 3, and 3 reaches back through 2. The second component is {2, 3}. The condensed graph has the single arrow from {0, 1} to {2, 3}, because 1 -> 2 crosses the boundary.
This example has two SCCs of size two, joined by one arrow. Work through it on paper once, to make sure the reversed walks stop where you expect.
Cost
Each pass visits every vertex once and every arrow once. Building the reversed graph also takes one pass over the arrows. The total time is proportional to the number of vertices plus the number of edges. The extra memory is the reversed graph, plus a few arrays with one entry per vertex.
The code above uses recursion. A very long chain of vertices can make the recursion deeper than the call stack allows, and the program may then crash. Turning the two recursive functions into loops with an explicit stack of vertices avoids this. That version is longer, and the logic stays the same.
Common mistakes
Reading the finish order from the first entry. The list is built in finish order, so the first entry is the vertex that finished first. Pass 2 needs the last entry first. If your components look like one big group, check this loop first.
Walking the original graph in pass 2. The pass 2 walk must use the reversed graph. Using the original graph gives one component for many graphs, as the trace above shows.
Forgetting the placed check in pass 2. The walk must skip any vertex that already has a component number. Without that check, the walk can visit placed vertices again and mix components. It can also run forever on a graph with a loop.
Forgetting the placed check in the outer loop of pass 2. The outer loop should start a walk only from a vertex that is not yet placed. Starting from a placed vertex creates an extra component with the same vertices.
Building the condensed graph with duplicate arrows. Many original arrows can cross between two boxes. A set of pairs removes duplicates. Without it, the condensed graph has repeated arrows, which does not change the answer but makes counts wrong.
Compiling with a signed loop counter. The code uses std::size_t for vertex numbers, because g.size() returns that type. A loop written as for (int i = 0; i < v.size(); ++i) compiles, but -Wall reports this:
warn.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]Use std::size_t or a range-based loop for vertex numbers, so the warning does not appear.
Missing include. This small test file, saved as nobrace.cpp, uses std::vector without including <vector>:
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
std::cout << v[0] << "\n";
}The compiler reports:
nobrace.cpp:4:10: error: ‘vector’ is not a member of ‘std’
4 | std::vector<int> v = {1, 2, 3};
| ^~~~~~
nobrace.cpp:2:1: note: ‘std::vector’ is defined in header ‘<vector>’; this is probably fixable by adding ‘#include <vector>’The compiler prints more lines after these, such as error: expected primary-expression before ‘int’, because the rest of the file depends on the missing name. The first error line tells you the real cause.
Practice
Exercise 1. A graph has the arrows 0 -> 1, 1 -> 2, 2 -> 1, 2 -> 3 and 3 -> 4, and 4 -> 3. List its SCCs, and list the arrows of its condensed graph.
Show the answer
The SCCs are {0}, {1, 2} and {3, 4}. Vertices 1 and 2 reach each other through the two arrows between them. Vertices 3 and 4 do the same. Vertex 0 has no arrow coming back to it, so it stands alone. The condensed graph has the arrows {0} -> {1, 2} and {1, 2} -> {3, 4}.
Exercise 2. A graph has four vertices and the arrows 0 -> 1, 1 -> 2 and 2 -> 3. How many SCCs does it have?
Show the answer
Four. A walk along the arrows only goes forward, so no two vertices can reach each other. Each vertex is its own SCC, and the condensed graph has the same shape as the original graph.
Exercise 3. Write the reversed graph of this graph: 0 -> 1, 0 -> 2 and 2 -> 1.
Show the answer
The reversed graph has the arrows 1 -> 0, 2 -> 0 and 1 -> 2. As adjacency lists, vertex 0 has no neighbours, vertex 1 has neighbours 0 and 2, and vertex 2 has neighbour 0.
Exercise 4. Explain in your own words why pass 2 must use the reversed graph. Use the graph 0 -> 1 and 1 -> 0 plus 1 -> 2 as the example.
Show the answer
In the original graph, a walk from vertex 0 reaches 1 and 2, so it would collect vertex 2 into the same box as 0 and 1. That is wrong, because 2 cannot reach 0 or 1. In the reversed graph, the arrow 1 -> 2 becomes 2 -> 1, so no walk from 0 can reach 2. The walk stops at {0, 1}.
Exercise 5. Why can the condensed graph never contain a cycle?
Show the answer
Suppose boxes A and B pointed at each other. Then some vertex in A could reach some vertex in B, and some vertex in B could reach back to A. Those vertices would be able to reach each other, so they would be in one SCC. Then A and B would be the same box, which contradicts the assumption that they are two boxes.
Summary
- A strongly connected component is a largest set of vertices where every vertex can reach every other.
- Kosaraju's algorithm runs a DFS on the graph to record a finish order, then walks the reversed graph in the order from last to first.
- Each walk in the second pass collects exactly one SCC, so the algorithm takes time proportional to vertices plus edges.
- The condensed graph replaces each SCC with one box, and it is always a DAG, so it can be ordered with a topological sort.
- Pass 2 must use the reversed graph and the reversed reading order. Either mistake gives one big component.