module Task11 where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set
import Control.Lens
import Control.Applicative (liftA2)
import Control.Monad
import Control.Monad.State
import Control.Monad.Reader
import Control.Monad.Writer
import Control.Monad.Except


type Vertex = Char
type Edge = (Vertex, Vertex)
type Stamp = (Vertex, Int, Int)

dfs :: Vertex -> [Edge] -> State (Int, Set Vertex) [Stamp]
dfs v es = do
    _2 %= Set.insert v
    tDisc <- gets fst
    _1 += 1
    let succs = snd <$> filter ((== v).fst) es
    succStamps <- forM succs $ \s -> do
        visited <- gets snd
        if s `elem` visited then return []
                            else dfs s es
    tFin <- gets fst
    _1 += 1
    return $ (v, tDisc, tFin) : concat succStamps

dfs' :: Vertex -> [Edge] -> [Stamp]
dfs' v es = evalState (dfs v es) (1, Set.empty)


g :: [Edge]
g = [ ('a','b')
    , ('a','c')
    , ('a','d')
    , ('b','c')
    , ('b','e')
    , ('c','b')
    , ('c','d')
    , ('c','c')
    , ('d','a')
    , ('e','b')
    ]