import Array
import ST

type Vertex = Int
type Graf = Array Vertex [Vertex]

-- dfs pomoci ST

dfs::Graf->Vertex->[Vertex]
dfs g v = runST (dfsST g v)

dfsST::Graf->Vertex->ST s [Vertex]
dfsST g v =
  do
    marks <- newSTArray (bounds g) False
    return $ reverse $ dfsAcc g v marks []

dfsAcc::Graf->Vertex->STArray s Vertex Bool->[Vertex]->[Vertex]
dfsAcc g v marks acc =
  do
    m <- 
  | marks ! v = (marks, acc)
  | otherwise = foldl visit (marks // [(v,True)], v:acc) (g ! v)
  where
    visit (marks', acc') v' = dfsAcc g v' marks' acc'

-- problem -- casova slozitost O(n^2 + e) -- (//) ma linearni casovou
-- slozitost (pole je nutne zkopirovat, jelikoz muzeme pristupovat ke
-- starsim verzim)

-- lze zrychlit pouzitim stromu na O(n log n + e)
-- slozitost O(n+e) jde dosahnout pomoci ruznych vice ci mene pochybnych
-- rozsireni jazyka

gph::Graf
gph = array (1,5) [(1,[2,3]),(2,[4,5]),(3,[4]),(4,[]),(5,[])]