【AtCoder版！蟻本】ABC002 D - 派閥【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているABC002 DをPythonで解いていきます。

リンク

atcoder.jp

AtCoder Beginner Contest 002 D - 派閥

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。
人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

制約

・N (1≦N≦12)
・M (0≦M≦N(N−1)/2)
・xi と yi はともに整数で、1 ≦ xi < yi ≦ Nを満たす。
・i≠j のとき、( xi , yi ) ≠ ( xj , yj ) であることが保証されている。

解答例

#bit全探索 組み合わせ

import itertools
n, m = map(int,input().split())

friend = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    x, y = map(int,input().split())
    friend[x][y] = 1
    friend[y][x] = 1

ans = 0
for bit in range(2**n):
    group = [] # 派閥のリスト
    for i in range(n):
        if (bit >> i) & 1:
            group.append(i+1) # bitが1ならiさんを派閥にくわえる
    # 派閥の人が互いに知り合いか判定フラグ
    flag = 1
    for j in itertools.combinations(group,2):
        if friend[j[0]][j[1]] == 0:
            flag = 0
            break
    if flag == 1:
        ans = max(ans,len(group))

print(ans)

解説

問題文の3行くらいはあまり読む意味がないですが…(^_^;)
N人の議員がいて 互いが知り合いなら派閥に入れます。
最大で何人の派閥が作れるか答える問題です。

N人の議員にたいしてbit全探索を行います。
bitが1の議員は派閥に入ると仮定して派閥候補リストgroupにいれます。
派閥候補が決まれば、そのリストから2人の組み合わせを試していきます。
friendリストを参照して、そのふたりが知り合いか判定します。
もし候補のすべての議員が互いに知り合いならansと比較して、大きいほうを代入していきます。

ループを抜けてansを出力すればACでした！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク