Algorithm
List> kosaraju(List[] graph, List[] revGraph) {
int V = graph.length;
boolean[] visited = new boolean[V];
Deque order = new ArrayDeque<>();
for (int i = 0; i < V; i++)
if (!visited[i]) dfs1(i, graph, visited, order);
Arrays.fill(visited, false);
List> sccs = new ArrayList<>();
while (!order.isEmpty()) {
int u = order.pop();
if (!visited[u]) {
List comp = new ArrayList<>();
dfs2(u, revGraph, visited, comp);
sccs.add(comp);
}
}
return sccs;
}
Advertisement
Why it works
First DFS orders by finish time. Second DFS on reversed graph, starting from highest finish times, discovers exactly one SCC at a time.
Advertisement
vs Tarjan
Kosaraju: 2 DFS passes, easier to understand. Tarjan: 1 pass with low-link, more memory-efficient (no reverse graph).
Complexity
O(V+E) time. O(V+E) extra space for reverse graph.