Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. {- Karol Samborski -}
  2. module Main where
  3.  
  4. import Data.List
  5. import Data.Array
  6.  
  7. type Edge   = Int
  8. data Vertex = Vertex { nr :: Int, edges :: [Edge], low :: Int }
  9.  
  10. type Bridge = (Int, Int)
  11.  
  12. findBridges :: Array Int Vertex -> [Bridge]
  13. findBridges vs = foldr (\(i, v) acc ->
  14.     if low v == nr v
  15.         then (zip [i,i..] $ filter (\e -> low (newVs!e) /= low v) $ edges v) ++ acc
  16.         else acc) [] $ assocs newVs
  17.   where
  18.     newVs = dfsBridges [1] vs 1
  19.  
  20. dfsBridges :: [Int] -> Array Int Vertex -> Int -> Array Int Vertex
  21. dfsBridges []     ar _ = ar
  22. dfsBridges (v:vs) ar d = dfsArray // [(v, (dfsArray!v) { low = foldr (\e l ->
  23.     if (nr $ dfsArray!e) > (-1) && e /= (d-1) && (low $ dfsArray!e) < l
  24.         then (low $ dfsArray!e)
  25.         else l) d $ edges $ dfsArray!v})]
  26.   where
  27.     initArr = ar//[(v, (ar!v) {nr = d, low = d})]
  28.     stack = foldr (\e l ->
  29.         if (nr $ initArr!e) > (-1)
  30.             then l
  31.             else l ++ [e]) vs $ edges $ ar!v
  32.     dfsArray = dfsBridges stack initArr (d+1)
  33.  
  34. main :: IO ()
  35. main = do
  36.     count <- (getLine >>= readIO) :: IO Int
  37.     v <- mapM (\i -> do
  38.         l <- (getLine >>= readIO) :: IO [Int]
  39.         return $ Vertex (-1) l (-1)) [1..count]
  40.     putStrLn $ show $ findBridges $ listArray (1,count) v