tsort.hs

import Data.List

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

getEdges :: IO [Edge]
getEdges = do
  putStr "> "
  line <- getLine
  if line == ""
    then return []
    else do
      let vs = words line
      if length vs /= 2
        then do 
          print "input edge like \"2 5\""
          getEdges
        else do
          es <- getEdges
          return $ (readInt (vs!!0), readInt (vs!!1)) : es
  where    
  readInt :: String -> Int
  readInt = read

isSubsetOf :: Eq a => [a] -> [a] -> Bool
isSubsetOf xs ys = and [x `elem` ys | x <- xs]

verticies :: [Edge] -> [Vertex]
verticies es = map head . group . sort . concat $ [[v, w] | (v, w) <- es]

getSource :: [Edge] -> [(Vertex, [Vertex])]
getSource es = [(v, [fst e | e <- es, snd e == v]) | v <- verticies es]

tsort :: [Edge] -> [Vertex]
tsort es = tsort' [] (getSource es)
  where
  tsort' accum source 
    | length accum == length source = accum
    | otherwise = let novel = [fst s | s <- source, not (fst s `elem` accum), snd s `isSubsetOf` accum]
                  in  tsort' (accum ++ novel) source

main = getEdges >>= print . tsort

とりあえず書いてみただけなので効率は悪い

$ runhaskell tsort.hs
> 7 5
> 7 8
> 5 11
> 3 8
> 3 10
> 11 2
> 11 9
> 11 10
> 8 9
[3,7,5,8,11,2,9,10]

入力例はwikiから