[Python] ABC002 D by python

2019/4/17 アルゴリズム, プログラミング

D – 派閥

from itertools import combinations

n, m = map(int, input().split())
matrix_relations = [[False] * n for _ in range(n)]
# matrixに関係を格納する。
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)

解けなかった…。

メモ