| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Scc
Description
It calculates the strongly connected components of directed graphs.
Example
>>>import AtCoder.Scc qualified as Scc>>>gr <- Scc.new 4 -- 0 1 2 3>>>Scc.nScc gr4>>>Scc.addEdge gr 0 1 -- 0 -> 1 2 3>>>Scc.addEdge gr 1 0 -- 0 == 1 2 3>>>Scc.addEdge gr 1 2 -- 0 == 1 -> 2 3>>>Scc.scc gr[[3],[0,1],[2]]
Since: 1.0.0
Documentation
new :: PrimMonad m => Int -> m (SccGraph (PrimState m)) #
Creates a directed graph with \(n\) vertices and \(0\) edges.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0
addEdge :: (HasCallStack, PrimMonad m) => SccGraph (PrimState m) -> Int -> Int -> m () #
Adds a directed edge from the vertex from to the vertex to.
Constraints
- \(0 \leq \mathrm{from} \lt n\)
- \(0 \leq \mathrm{to} \lt n\)
Complexity
- \(O(1)\) amortized
Since: 1.0.0
scc :: PrimMonad m => SccGraph (PrimState m) -> m (Vector (Vector Int)) #
Returns the list of the "list of the vertices" that satisfies the following.
Each vertex is in exactly one "list of the vertices". Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined. The list of "list of the vertices" are sorted in topological order, i.e., for two vertices \(u, v\) in different strongly connected components, if there is a directed path from \(u\) to \(v\), the list containing \(u\) appears earlier than the list containing \(v\).
Complexity
- \(O(n + m)\), where \(m\) is the number of added edges.
Since: 1.0.0