Kosaraju's algorithm
Kosaraju's algorithm is a method used to find the strongly connected components (SCCs) of a directed graph. It operates in two main phases: first, it performs a depth-first search (DFS) to determine the finishing order of the vertices. This order is crucial for the next step, where the graph is transposed, meaning all edges are reversed.
In the second phase, the algorithm again uses DFS, but this time on the transposed graph, processing vertices in the order determined earlier. Each DFS call identifies a strongly connected component, allowing the algorithm to efficiently group vertices that are mutually reachable within the graph.