D - 派閥

問題

https://atcoder.jp/contests/abc002/tasks/abc002_4 (新しいタブで開く)

問題文

$N$ 人の人と、 $M$ 個の人間関係 $(x, y)$ がある。
$(x, y)$ は、 $x$ と $y$ が知り合いであることを表す。
$N$ 人のうちから、何人かを選んで、その人たちがすべて互いに知り合いであるようにする。
このとき、選んだ人たちの最大人数は？

制約

• $1 \le N \le 12$
• $0 \le M \le \frac{N(N-1)}{2}$
• $1 \le x < y \le N$
• $i \ne j \Rightarrow (x_i, y_i) \ne (x_j, y_j)$

サンプル

I/O 1

5 3
1 2
2 3
1 3

3

I/O 2

5 3
1 2
2 3
3 4

2

I/O 3

7 9
1 2
1 3
2 3
4 5
4 6
4 7
5 6
5 7
6 7

4

I/O 4

12 0

1

考察

$N$ が小さいので bit 全探索する。
グラフは set で管理するとかなり楽できる。
(隣接行列で表すと計算量は削減できるけど...)

コード

https://atcoder.jp/contests/abc002/submissions/27938791 (新しいタブで開く)

int main() {
  int n, m;
  cin >> n >> m;
  vector Graph(n, set<int>());
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    Graph[--a].insert(--b);
    Graph[b].insert(a);
    Graph[a].insert(a);
    Graph[b].insert(b);
  }
  int ans = 1;
  rep(bit, 1 << n) {
    set<int> s;
    rep(i, n) if (bit & 1 << i) s.insert(i);
    bool chk = true;
    for (int x : s)
      for (int y : s) {
        if (!Graph[x].count(y)) chk = false;
      }
    if (chk) ans = max(ans, int(s.size()));
  }
  cout << ans << endl;
  return 0;
}