【競プロ】過去問精選100問「AtCoder Beginner Contest 002 D - 派閥」解法

def main():
    N, M = map(int, input().split(" "))
    cons = [list(map(int, input().split(" "))) for i in range(M)]

    list_congress = [i for i in range(1, N + 1)]  # 議員全員のリストを作成
    ans = 1  # 1人は絶対入れられるので答えが1以下になることはない

    # ビット全探索で議員の組み合わせパターンを全て確認
    for i in range(2 ** N):
        candidates = []  # 派閥に入れる議員のリスト
        for j in range(N):
            if (i >> j) & 1:
                index = N - 1 - j
                candidates.append(list_congress[index])  # 派閥に入れる議員を追加

        # 全ての議員同士の繋がりが存在するかを確認する
        for index, can in enumerate(candidates):  # 任意の議員が先頭に来るように並び替え
            tmp = [candidates[index]] + candidates[:index] + candidates[index + 1:]

            # 先頭の議員と他の全ての議員との間に繋がりが存在するか確認
            n = 1
            while n < len(tmp):
                tmp2 = [tmp[0], tmp[n]]
                tmp2.sort()
                if tmp2 not in cons:  # 議員間の繋がりが存在するか確認
                    break
                else:
                    n += 1
            else:
                continue
            break
        else:
            ans = max(ans, len(candidates))  # 全ての議員同士のつながりが存在したらansを更新

    print(ans)


if __name__ == '__main__':
    main()