Submission #180974

---

Source Code Expand

#!/usr/bin/env python2.7

import sys

from cStringIO import StringIO
from collections import namedtuple

import unittest
import cProfile

class Edge(namedtuple("Edge", "a b")):
    pass

def main():
    N, G, E  = (int(x) for x in sys.stdin.readline().split())
    p = (int(x) for x in sys.stdin.readline().split())
    Es = []
    for _ in xrange(E):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        Es.append(Edge(a, b))

    print solve(N, p, Es)

def genpat(Es):
    N = len(Es)
    for k in xrange(2**N):
        k = format(k, str(N)+'b')
        yield [Es[i] for i in xrange(N) if k[i] == '1']

def solve(N, p, Es):
    if len(Es) > 12:
        return "GIVEUP"
    p = set(p)

    g = { i: list() for i in xrange(N)}
    for e in Es:
        g[e.a].append(e.b)
        g[e.b].append(e.a)

    # filter linked
    fset = set()
    cset = set([0])
    while len(cset) != 0:
        i = cset.pop()
        nset = set(g[i])
        fset.add(i)
        nset -= fset
        cset |= nset
    p &= fset

    best = len(p)
    for subs in genpat(Es):

        L = len(Es) - len(subs)

        g = { i: list() for i in xrange(N)}
        for e in subs:
            g[e.a].append(e.b)
            g[e.b].append(e.a)

        fset = set()
        cset = set([0])
        while len(cset) != 0:
            i = cset.pop()
            nset = set(g[i])
            fset.add(i)
            nset -= fset
            cset |= nset

        L += len(p & fset)
        
        if L < best:
            best = L

    return best
    
class Test(unittest.TestCase):

    @staticmethod
    def tryone(indata):
        sys.stdin = StringIO(indata)
        out = sys.stdout = StringIO()
        main()
        return out.getvalue()

    def test50(self):
        self.assertEqual(solve(4, [2, 3],
                        [Edge(0,1), Edge(1,2), Edge(1,3)]), 1)
        self.assertEqual(solve(4, [3],
                        [Edge(0,1), Edge(0,2), Edge(1,3), Edge(2,3)]), 1)
        self.assertEqual(solve(10, [7, 8, 9],
                        [
                            Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4),
                            Edge(1,5), Edge(2,5), Edge(5,6), Edge(6,7),
                            Edge(6,8), Edge(3,9), Edge(4,9),
                        ]), 2)

    def test90(self):
        self.assertEqual(self.tryone("""\
4 2 3
2 3
0 1
1 2
1 3
"""), """1\n""")

if __name__ == '__main__':
    if len(sys.argv) > 1:
        print "_/" * 30 + str(sys.argv)
        if sys.argv[1] == '-p':
            sys.argv.pop(1)
            cProfile.run("unittest.main(exit=False, failfast=True)", sort='time')
        else:
            unittest.main()
    else:
        main()

Submission Info

Judge Result