content: -- | It calculates the strongly connected components of directed graphs.
  --
  -- ==== __Example__
  -- Create a `SccGraph`:
  --
  -- >>> import AtCoder.Scc qualified as Scc
  -- >>> gr <- Scc.new 4     -- 0    1    2    3
  -- >>> Scc.nScc gr
  -- 4
  --
  -- Add edges and get SCC of the graph:
  --
  -- >>> 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]]
  --
  -- See also the @scc@ function in @AtCoder.Extra.Graph@ module that computes SCC for a CSR.
  --
  -- @since 1.0.0.0
  module AtCoder.Scc (SccGraph, nScc, new, addEdge, scc) where
  
  import AtCoder.Internal.Assert qualified as ACIA
  import AtCoder.Internal.Scc qualified as ACISCC
  import Control.Monad.Primitive (PrimMonad, PrimState)
  import Data.Vector qualified as V
  import Data.Vector.Unboxed qualified as VU
  import GHC.Stack (HasCallStack)
  
  -- | Directed graph for calculating strongly connected components.
  --
  -- @since 1.0.0.0
  newtype SccGraph s = SccGraph (ACISCC.SccGraph s)
  
  -- | Returns the number of vertices in the SCC graph.
  --
  -- @since 1.0.0.0
  {-# INLINE nScc #-}
  nScc :: SccGraph s -> Int
  nScc (SccGraph g) = ACISCC.nScc g
  
  -- | Creates a directed graph with \(n\) vertices and \(0\) edges.
  --
  -- ==== Constraints
  -- - \(0 \leq n\)
  --
  -- ==== Complexity
  -- - \(O(n)\)
  --
  -- @since 1.0.0.0
  {-# INLINE new #-}
  new :: (PrimMonad m) => Int -> m (SccGraph (PrimState m))
  new n = SccGraph <$> ACISCC.new n
  
  -- | 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.0
  {-# INLINE addEdge #-}
  addEdge :: (HasCallStack, PrimMonad m) => SccGraph (PrimState m) -> Int -> Int -> m ()
  addEdge (SccGraph gr) from to = do
    let n = ACISCC.nScc gr
    let !_ = ACIA.checkCustom "AtCoder.Scc.addEdge" "`from` vertex" from "the number of vertices" n
    let !_ = ACIA.checkCustom "AtCoder.Scc.addEdge" "`to` vertex" to "the number of vertices" n
    ACISCC.addEdge gr from to
  
  -- | 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.0
  {-# INLINE scc #-}
  scc :: (PrimMonad m) => SccGraph (PrimState m) -> m (V.Vector (VU.Vector Int))
  scc (SccGraph g) = ACISCC.scc g
  