Submission #18240136

---

Source Code Expand

def maximum_independent_set(n, edge):
    n1 = n // 2
    n2 = n - n1
    maxlen = 0
    res = 0

    ind1 = [True] * (1 << n1)
    ind2 = [True] * (1 << n2)
    nc = [(1 << n2) - 1] * (1 << n1)
    mis = [0] * (1 << n2)
    mislen = [0] * (1 << n2)

    for u, v in edge:
        if u < n1 and v < n1:
            ind1[1 << u | 1 << v] = False
        elif u < n1:
            nc[1 << u] ^= 1 << (v - n1)
        elif v < n1:
            nc[1 << v] ^= 1 << (u - n1)
        else:
            ind2[1 << (u - n1) | 1 << (v - n1)] = False

    for bit in range(1 << n1):
        if ind1[bit]: continue
        for i in range(n1):
            ind1[bit | 1 << i] = False

    for bit in range(1 << n1):
        for i in range(n1):
            if (bit >> i) & 1: continue
            nc[bit | 1 << i] = nc[bit] & nc[1 << i]

    for bit in range(1 << n2):
        if ind2[bit]: continue
        for i in range(n2):
            ind2[bit | 1 << i] = False

    for bit in range(1 << n2):
        if not ind2[bit]: continue
        mis[bit] = bit
        for i in range(n2):
            if (bit >> i) & 1:
                mislen[bit] += 1

    for bit in range(1 << n2):
        for i in range(n2):
            if (bit >> i) & 1: continue
            if mislen[bit | 1 << i] < mislen[bit]:
                mislen[bit | 1 << i] = mislen[bit]
                mis[bit | 1 << i] = mis[bit]

    for bit in range(1 << n1):
        tmp = 0
        if not ind1[bit]: continue
        for i in range(n1):
            if (bit >> i) & 1:
                tmp += 1
        tmp += mislen[nc[bit]]
        if maxlen < tmp:
            maxlen = tmp
            res = (mis[nc[bit]] << n1) + bit

    res = [i for i in range(N) if (res >> i) & 1]
    return res

N, M = map(int, input().split())
E = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

print(len(maximum_independent_set(N, E)))

Submission Info

Judge Result