Submission #3595106

---

Source Code Expand

import copy
N, M = [int(s) for s in input().rstrip().split()]
connect = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(s) for s in input().rstrip().split()]
    connect[x-1].append(y-1)
    connect[y-1].append(x-1)

# 全ての派閥パターンを調べる    
pattern = 2 ** N -1
group = [[] for _ in range(pattern)] # 派閥に属している議員
for p in range(pattern):
    bi = str(bin(p+1))[2:]
    bi = bi[::-1]
    for i, b in enumerate(bi):
        if b == '1':
            group[p].append(i)

max_members = 0  # 最大派閥人数            
for members in group:
    if len(members) == 1:
        if max_members == 0:
            max_members = 1
        continue
    judge = True
    for member in members:
        others = copy.deepcopy(members)
        others.remove(member)
        for other in others:
            if other not in connect[member]:
                judge = False
    if judge:
        if len(members) > max_members:
            max_members = len(members)

print(max_members)

Submission Info

Judge Result