blob: 2bb9b90d05e9e16763a0b61d17bdd75a02f10999 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import qualified Data.IntSet as IntSet
import Data.Array
newtype Graph = Graph { neighbors :: Array Int [Int] }
readGraph :: [[Int]] -> Graph
readGraph ([n] : edges) = ans where
ans = Graph $ accumArray (flip (:)) [] (1, n) edgesTwice
edgesTwice = concat [[(u, v), (v, u)] | [u, v] <- edges]
readGraph _ = error "readGraph: bad format"
bfs :: Graph -> Int -> Array Int Int
-- returns an array with the distance from each node to the start node
bfs g start = array (bounds (neighbors g)) $ assocList where
assocList = _bfs 0 IntSet.empty (IntSet.singleton start)
_bfs dist visited currs = if IntSet.null currs
then []
else map (\x -> (x, dist)) currli ++ _bfs (dist+1) nvisit ncurr where
currli = IntSet.toList currs
nvisit = IntSet.union visited currs
ncurr = IntSet.difference nbrs nvisit
nbrs = IntSet.fromList (concatMap (neighbors g !) currli)
solve :: [[Int]] -> [Int]
solve li@(_:edges) = map ((`mod` 2) . (bfs (readGraph li) 1 !) . head) edges
solve _ = error "no input?"
parse :: String -> [[Int]]
parse = map (map read . words) . lines
|
