Jikka- A transpiler from Python to C++ for competitive programming
Safe HaskellNone




decomposeToStronglyConnectedComponents :: Graph -> Vector Int Source #

decomposeToStronglyConnectedComponents does SCC in \(O(V + E)\) using Kosaraju's algorithm. It takes a digraph \(G = (V, E)\) as an adjacent list \(g : V \to V^{\lt \omega}\), and returns an mapping \(f : V \to V'\) for the SCC DAG \(G' = (V', E')\). The indices of vertices of the SCC DAG are topologically sorted.

topologicalSort :: Graph -> Vector Int Source #

topologicalSort does topological sort in \(O(V + E)\) using Tarjan's algorithm. The input is an adjacent list of a DAG.