ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.Internal.Scc

Description

Implementation of Strongly Connected Components calculation. Use Scc instead.

Since: 1.0.0

Synopsis

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