Kosaraju

Computes strongly connected components of a directed graph using the Kosaraju-Sharir algorithm. See Kosaraju, 1962. See Kosaraju's Algorithm. See A Strong ConnectivityLazy Algorithm....

The algorithm makes two passes:

Pass 1 — post-order DFS over the reversed graph, collecting vertices in reverse finish order. Because ListJournal prepends, result.result.map(_._1).toList already yields vertices with the last-finished vertex at the head — exactly the seed order required for pass 2.

Pass 2 — DFS over the original graph, seeding vertices in the order produced by pass 1, with a shared visited set carried across seeds. Each DFS tree in pass 2 is exactly one SCC.

NOTE: intended for directed graphs only. For undirected graphs see ConnectedComponents.

When applied to a Directed Acyclic Graph (DAG), the result is a topologically sorted set of SCCs, each of which holds only one vertex.