問題
https://atcoder.jp/contests/abc002/tasks/abc002_4 (新しいタブで開く)
問題文
人の人と、 個の人間関係 がある。
は、 と が知り合いであることを表す。
人のうちから、何人かを選んで、その人たちがすべて互いに知り合いであるようにする。
このとき、選んだ人たちの最大人数は?
制約
サンプル
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
考察
が小さいので 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; }