AtCoder.Internal.Scc

Implementation of Strongly Connected Components calculation. Use Scc instead.

Since: 1.0.0

Internal SCC

data SccGraph s

Graph for collecting strongly connected components.

Since: 1.0.0

Constructor

new :: PrimMonad m => Int -> m (SccGraph (PrimState m))

\(O(n)\) Creates SccGraph of \(n\) vertices.

Since: 1.0.0

Modifying the graph

addEdge :: PrimMonad m => SccGraph (PrimState m) -> Int -> Int -> m ()

\(O(1)\) amortized. Adds an edge to the graph.

Since: 1.0.0

SCC calculation

sccIds :: PrimMonad m => SccGraph (PrimState m) -> m (Int, Vector Int)

\(O(n + m)\) Returns a pair of (# of scc, scc id).

Since: 1.0.0

scc :: PrimMonad m => SccGraph (PrimState m) -> m (Vector (Vector Int))

\(O(n + m)\) Returns the strongly connected components.

Since: 1.0.0