component = 0
for u in V:
    cc[u] = UNLABELLED
for u in V:
    if cc[u] == UNLABELLED:
        visit(u, component)
        component = component + 1

visit(u, label):
    cc[u] = label
    for v in adjacency[u]:
        if cc[v] == UNLABELLED:
            visit(v, label)

rotatePoly :: Polygon -> Double -> Polygon
rotatePoly ps theta =
  (translate c . map turn . translate (-cx,-cy)) ps
  where
    c@(cx,cy) = centroid ps
    turn (x,y) = (cos theta*x + sin theta*y,
                 -sin theta*x + cos theta*y)

translate :: Point -> Polygon -> Polygon
translate (u,v) = map (\(x,y) -> (x+u,y+v))

centroid :: Polygon -> Point
centroid [] = error "centroid: empty vertex list"
centroid ps = (sx/n,sy/n)
  where
    (sx,sy) = foldr (\(x,y) (u,v) -> (x+u,y+v)) (0,0) ps
    n = fromIntegral (length ps)

regular :: Polygon -> Bool
regular ps
  | length ps < 3 = False
  | otherwise = norm2 (head es) > 0 && (fits 1 || fits (-1))
  where
    es = [ (u-x,v-y) | ((x,y),(u,v)) <- edges ps ]
    angle = 2*pi / fromIntegral (length ps)
    norm2 (x,y) = x*x+y*y
    close x y = abs (x-y) <= 1e-10 * max 1 (max (abs x) (abs y))
    same (x,y) (u,v) = close x u && close y v
    turn s (x,y) = (cos angle*x - s*sin angle*y,
                    s*sin angle*x + cos angle*y)
    fits s = and (zipWith (\a b -> same (turn s a) b)
                          es (tail es ++ [head es]))

edges :: Polygon -> [(Point,Point)]
edges [] = []
edges ps = zip ps (tail ps ++ [head ps])

perimeter :: Polygon -> Double
perimeter = total . edges
  where total [] = 0
        total ((p,q):es) = distBetween p q + total es

perimeterFold :: Polygon -> Double
perimeterFold = foldr (\(p,q) s -> distBetween p q + s) 0 . edges

distBetween :: Point -> Point -> Double
distBetween (x,y) (u,v) = sqrt ((x-u)^2 + (y-v)^2)

type Point = (Double,Double)
type Polygon = [Point]

eval :: String -> Maybe Int
eval input = foldMaybe first Nothing (parseInt input)
  where
    first (a,rest) = foldMaybe (second a) Nothing (parseOp rest)
    second a (op,rest) = foldMaybe (finish a op) Nothing (parseInt rest)
    finish a op (b,rest)
      | null rest = Just (apply op a b)
      | otherwise = Nothing
    apply '+' a b = a+b
    apply '-' a b = a-b
    apply '*' a b = a*b
    apply '/' a b = a `div` b
    apply _ _ _ = error "unreachable: parseOp rejected this operator"

parseOp :: Parse Char
parseOp (c:cs)
  | c `elem` "+-*/" = Just (c,cs)
parseOp _ = Nothing

import Data.Char (isDigit, digitToInt)

type Parse a = String -> Maybe (a,String)

parseInt :: Parse Int
parseInt input =
  case span isDigit input of
    ([],_)  -> Nothing
    (ds,ys) -> Just (foldl (\n d -> 10*n + digitToInt d) 0 ds, ys)