Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- {- Karol Samborski -}
- module Main where
- import Data.List
- import Data.Array
- type Edge = Int
- data Vertex = Vertex { nr :: Int, edges :: [Edge], low :: Int }
- type Bridge = (Int, Int)
- findBridges :: Array Int Vertex -> [Bridge]
- findBridges vs = foldr (\(i, v) acc ->
- if low v == nr v
- then (zip [i,i..] $ filter (\e -> low (newVs!e) /= low v) $ edges v) ++ acc
- else acc) [] $ assocs newVs
- where
- newVs = dfsBridges [1] vs 1
- dfsBridges :: [Int] -> Array Int Vertex -> Int -> Array Int Vertex
- dfsBridges [] ar _ = ar
- dfsBridges (v:vs) ar d = dfsArray // [(v, (dfsArray!v) { low = foldr (\e l ->
- if (nr $ dfsArray!e) > (-1) && e /= (d-1) && (low $ dfsArray!e) < l
- then (low $ dfsArray!e)
- else l) d $ edges $ dfsArray!v})]
- where
- initArr = ar//[(v, (ar!v) {nr = d, low = d})]
- stack = foldr (\e l ->
- if (nr $ initArr!e) > (-1)
- then l
- else l ++ [e]) vs $ edges $ ar!v
- dfsArray = dfsBridges stack initArr (d+1)
- main :: IO ()
- main = do
- count <- (getLine >>= readIO) :: IO Int
- v <- mapM (\i -> do
- l <- (getLine >>= readIO) :: IO [Int]
- return $ Vertex (-1) l (-1)) [1..count]
- putStrLn $ show $ findBridges $ listArray (1,count) v
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement