Submission #225860

---

Source Code Expand

import Control.Applicative
import Control.Monad

main :: IO ()
main = do
  [n, m] <- makeInt <$> getLine
  edges <- replicateM m $ makeInt <$> getLine
  putStrLn $ show $ solve n edges

makeInt :: String -> [Int]
makeInt line = map read $ words line

geneid :: [Int] -> Int
geneid (a:b:_) = (min a b) * 100 + (max a b)

nSets :: Int -> [[Int]]
nSets 1 = [[], [1]]
nSets n = ret0 ++ ret1
          where ret0 = nSets (n-1)
                ret1 = map (n:) ret0

solve :: Int -> [[Int]] -> Int
solve n edges = foldl1 max $ map length valid 
                where edgeIds = map geneid edges
                      valid   = filter (isValid edgeIds) $ nSets n

isValid :: [Int] -> [Int] -> Bool
isValid eids []     = True
isValid eids (m:ms) = (isAllFriend eids m ms) && (isValid eids ms)

isAllFriend :: [Int] -> Int -> [Int] -> Bool
isAllFriend eids a []     = True
isAllFriend eids a (o:os) = (isFriend eids a o) && (isAllFriend eids a os)

isFriend :: [Int] -> Int -> Int -> Bool
isFriend eids a b = eid `elem` eids
                    where eid = geneid [a,b]

Submission Info

Judge Result