やっとビット全探索に慣れてきた気がする

今回の問題はざっくりいうと、N人の議員がいて、M個の知り合い関係があって、派閥に含まれる議員は全員知り合いという条件のとき、派閥の最大人数は何人になるかという問題。
atcoder.jp
まず着目するのはN人の最大値が12というところで、ビット全探索すれば通りになりそうと予想。
そこから12人の2人関係について列挙すると、通り。掛け合わせると265914で、計算量が億とかうん千万に届かないので、全列挙の方針で問題なしと判断しました。

ビットをたてた議員の組み合わせについて全員知り合いかどうか関係を全部チェックします。
最初は関係をtupleのsetに保存して、のオーダーでチェックしていたのですが、ロジックが甘いところがあり、74のテストケースで誤りが2つになりました。。。たぶん保存しているtupleの順番と検索しようとしている順番が逆のときにダメなんだと思います。(2, 3)の関係のときに、(3, 2)で検索してもだめという感じ。

関係をN * Nの配列に保存して、関係があれば1を入れるようにしました。

ただ、PyPyで提出したらなんとMLE（メモリオーバー）になってしまいました。。。
たまにあるのですが、なぜなのかいまだにわかりません。
Pythonで提出して無事にクリアしました。

ビット全探索に慣れてきた気がします。そしてこの感覚が勘違いでないことを祈りたい。あとこの感覚を忘れないうちに身体に染み込ませたい。

ビット全探索についてはけんちょんさんのとっても丁寧な説明で理解が進みました。

drken1215.hatenablog.com

from itertools import combinations
N, M = list(map(int, input().split()))
friends = [[0 for _ in range(N)] for _ in range(N)]
max_count = 0
if M == 0:
    print(1)
    exit()
for _ in range(M):
    x, y = list(map(int, input().split()))
    friends[x-1][y-1] = 1
    friends[y-1][x-1] = 1
for bit in range(1 << N):
    fr_list = []
    for i in range(N):
        if bit & (1 << i):
            fr_list.append(i)
    hantei = True
    for com in list(combinations(fr_list, 2)):
        if friends[com[0]][com[1]] == 0 or friends[com[1]][com[0]] == 0:
            hantei = False
            break
    if hantei:
        max_count = max(max_count, len(fr_list))
print(max_count)