Submission #70038977

---

Source Code Expand

N,M = map(int,input().split())
U,V = [],[]
for _ in range(M):
    u,v = map(int,input().split())
    U.append(u-1)
    V.append(v-1)


def partition_generator(N: int):
    """
    (list, list): 2つのサブセットで構成されるタプル。
    """
    for i in range(2**N):
        subset1 = []
        subset2 = []
        for j in range(N):
            if (i >> j) & 1:
                # ビットが1ならsubset2へ
                subset2.append(j)
            else:
                # ビットが0ならsubset1へ
                subset1.append(j)
        yield (subset1, subset2)

m = 10**9 #最小回数
for p in partition_generator(N):
    #subset内でのエッジを検出
    count = 0
    for i in range(M):
        if (U[i] in p[0]) == (V[i] in p[0]):
            count += 1
    if count < m:
        m = count
print(m)

Submission Info

Judge Result