Submission #4658054

---

Source Code Expand

from itertools import combinations

n, m = map(int, input().split())
matrix_relations = [[False] * n for _ in range(n)]
for _ in range(m):
    rel1, rel2 = map(int, input().split())
    matrix_relations[rel1-1][rel2-1] = True
    matrix_relations[rel2-1][rel1-1] = True

#議員は議員0から議員n-1まで
n_range = range(0, n)

ans = 1
    
for num in range(n, 0, -1):
    # num人のメンバーで構成される派閥を組み合わせで算出
    fraction = combinations(n_range, num)
    for relation in fraction:
        # print(relation)
        # その派閥を構成するのに必要な関係が入力されているかどうか行列から引っ張ってくる。
        judge = []
        for i, j in combinations(relation, 2):
            judge.append(matrix_relations[i][j])
        # 全てTrueなら必要な関係が入力されているのでその派閥は存在する。
        if all(judge):
            ans = num
            print(ans)
            # 最大派閥議員数が分かればよいので終了
            exit()

print(ans)

Submission Info

Judge Result