The challenge
Partition a directed graph into strongly connected components (SCCs), where every vertex inside one component can reach every other vertex in it.
Uses two DFS passes and a transpose graph with every directed edge reversed.
Example
The example has SCCs {A, B, F}, {C, D}, and {E}. On a DAG, every vertex is its own SCC.
Use the walkthrough below to inspect the input and each state change.
See Kosaraju, step by step
Follow the edges. Watch the state change.
Directed · 6 vertices · 7 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Step 01 / 15
Pass 1: compute finishing order.
Run DFS over every vertex in the original directed graph. Append a vertex only after all its neighbors finish.
for each unseen vertex: dfs1(vertex)Finish order · latest last
Empty
View input edges
A → B · B → F · F → A · B → C · C → D · D → C · D → E
Put it into code
Finishing order puts components in the right sequence for exploration on the reversed graph.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
def kosaraju(adj):
n = len(adj)
seen, finish = [False] * n, []
def dfs1(u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
dfs1(v)
finish.append(u) # Postorder, NOT discovery order.
for u in range(n):
if not seen[u]:
dfs1(u)
transpose = [[] for _ in range(n)]
for u in range(n):
for v in adj[u]:
transpose[v].append(u)
seen = [False] * n
components = []
def dfs2(u, component):
seen[u] = True
component.append(u)
for v in transpose[u]:
if not seen[v]:
dfs2(v, component)
for u in reversed(finish):
if not seen[u]:
component = []
dfs2(u, component)
components.append(component)
return components#include <algorithm>
#include <functional>
#include <vector>
std::vector<std::vector<int>> kosaraju(
const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size());
std::vector<bool> seen(n, false);
std::vector<int> finish;
std::function<void(int)> dfs1 = [&](int u) {
seen[u] = true;
for (int v : adj[u]) if (!seen[v]) dfs1(v);
finish.push_back(u);
};
for (int u = 0; u < n; ++u) if (!seen[u]) dfs1(u);
std::vector<std::vector<int>> transpose(n), components;
for (int u = 0; u < n; ++u)
for (int v : adj[u]) transpose[v].push_back(u);
std::fill(seen.begin(), seen.end(), false);
std::function<void(int, std::vector<int>&)> dfs2 =
[&](int u, std::vector<int>& component) {
seen[u] = true;
component.push_back(u);
for (int v : transpose[u]) if (!seen[v]) dfs2(v, component);
};
for (auto it = finish.rbegin(); it != finish.rend(); ++it) {
if (!seen[*it]) {
components.emplace_back();
dfs2(*it, components.back());
}
}
return components;
}