Kosaraju's Strongly Connected Components
Kosaraju's algorithm computes the Strongly Connected Components (SCCs) of a directed graph. An SCC is a subset of vertices in the graph for which every vertex is reachable from every other vertex in the subset, i.e. there exists a path between all pairs of vertices for the subset of vertices.
Kosaraju's algorithm runs in O(|V| + |E|) for directed graphs, where |V| the number of vertices and |E| is the
number of edges in the graph. So it runs in linear time.
Syntax
template <typename V, typename E>
sccs_t kosarajus_strongly_connected_components(const directed_graph<V, E>& graph);
- graph The graph for which to compute SCCs.
- return A type consisting of a vector of vectors representing SCCs.