import Array

-- graf reprezentovany seznamy sousedu
type Vertex = Int
type Graf = Array Vertex [Vertex]
type Marks = Array Vertex Bool

-- prohledavani do hloubky; vraci seznam vrcholu v poradi, v nemz
-- jsme je prosli

dfs::Graf->Vertex->[Vertex]
dfs g v = reverse $ snd $ dfsAcc g v marks []
  where
    vbounds = bounds g
    marks = array vbounds [(x,False) | x <- range vbounds]

dfsAcc::Graf->Vertex->Marks->[Vertex]->(Marks, [Vertex])
dfsAcc g v marks acc
  | 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,[])]