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.