ABC002 D - 派閥


Tags:cpatcoderbitexhaustive_searchdiff_experimentaldiff_cyan

問題

https://atcoder.jp/contests/abc002/tasks/abc002_4

問題文

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

制約

  • 1N121 \le N \le 12
  • 0MN(N1)20 \le M \le \frac{N(N-1)}{2}
  • 1x<yN1 \le x < y \le N
  • ij(xi,yi)(xj,yj)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

考察

NN が小さいので 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;
}