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