ABC 002 D - 派閥

はい、昨日完成できなかった問題。 布団に入ったあと、すぐに浮かんだ解答。 寝ようと思ったあとに、考えたり、思いつくのやめたい。 昨日より、すっきりしたし、簡単だと思った。 bit全探索で、頂点の組み合わせを出す。その後、それらの頂点が、互いに繋がっているときの、辺を無理やり出す。実際に、繋がっているか確認する。という手順でやった。n < 12なので、bit全探索をした上で組み合わせ計算しても間に合うくらいになってる(んだと思う)。

import itertools as it


def main():
    n, m = [int(i) for i in input().split()]
    table = [[False for j in range(n)] for i in range(n)]
    for i in range(m):
        x, y = [int(j) for j in input().split()]
        table[x-1][y-1] = True
    # bit全探索(頂点の組み合わせを出す)
    ans = 0
    for i in range(1<<n):
        tmp = []
        for j in range(n):
            if i >> j & 1:
                tmp.append(j)
        if len(tmp) < 2:
            continue
        edges = it.combinations(tmp, 2)
        if all(map(lambda x: table[x[0]][x[1]], edges)):
            ans = max(ans, len(tmp))
    print(ans if ans != 0 else 1)


if __name__ == '__main__':
    main()