D - 派閥

cpatcoderbitexhaustive searchdiff experimentaldiff cyan

最終更新日

問題

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

問題文

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

制約

サンプル

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;
}