pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>Expand description
[Generic] Compute the strongly connected components using Kosaraju’s algorithm.
This implementation is iterative and does two passes over the nodes.
§Arguments
g: a directed or undirected graph.
§Returns
Return a vector where each element is a strongly connected component (scc). The order of node ids within each scc is arbitrary, but the order of the sccs is their postorder (reverse topological sort).
For an undirected graph, the sccs are simply the connected components.
§Complexity
- Time complexity: O(|V| + |E|).
- Auxiliary space: O(|V|).
where |V| is the number of nodes and |E| is the number of edges.