F - Close Group https://atcoder.jp/contests/abc187/tasks/abc187_f

abc187_f.py

N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a][b] = True
    G[b][a] = True

ok = [True] * (1 << N)  # 各頂点が繋がっているかどうか?
for bit in range(1 << N):
    vs = []
    for i in range(N):
        if bit & (1 << i):
            vs.append(i)
    for i in range(len(vs)):
        if not ok[bit]:
            break
        for j in range(i + 1, len(vs)):
            if not G[vs[i]][vs[j]]:
                ok[bit] = False
                break

INF = 10**18
dp = [INF] * (1 << N)
dp[0] = 0
for bit in range(1 << N):
    if dp[bit] >= INF:
        continue
    cbit = (1 << N) - 1 - bit
    add = cbit
    while add > 0:
        if ok[add]:
            dp[bit | add] = min(dp[bit | add], dp[bit] + 1)
        add = (add - 1) & cbit

print(dp[(1 << N) - 1])