
このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】でまとめられている100問をPythonで解いています。
問題
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()