From 741e26dabbccb5821c79736590ad03286fe04f84 Mon Sep 17 00:00:00 2001 From: Determinant Date: Wed, 31 May 2017 21:23:39 -0400 Subject: one prob left for v9 --- 80-89/88.hs | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 80-89/88.hs (limited to '80-89/88.hs') diff --git a/80-89/88.hs b/80-89/88.hs new file mode 100644 index 0000000..6c1123c --- /dev/null +++ b/80-89/88.hs @@ -0,0 +1,22 @@ +import Data.List (partition, foldl') + +data Graph a = Graph [a] [(a, a)] deriving (Show, Eq) + +connComp :: Eq a => Graph a -> [[a]] + +connComp (Graph v e) = fst $ foldl' + (\(comps, vis) u -> if u `elem` vis then (comps, vis) + else let (s, vis') = dfs u vis in + (s:comps, vis')) + ([], []) v + where adjust u (a, b) + | a == u = [b] + | b == u = [a] + | otherwise = [] + dfs u vis + | u `elem` vis = ([], vis) + | otherwise = let vs = (e >>= (adjust u)) in + foldl' (\(s, vis') v -> + let (s', vis'') = dfs v vis' in + (s ++ s', vis'')) + ([u], u:vis) vs -- cgit v1.2.3