ABC002 D:派閥

競技プログラミング

C問題を埋めきったわけじゃないけど、ぼちぼちD問題も解いていこうと思う。

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

重みなし無向グラフ + bit探索の組み合わせ。D問題からはこういった複合的な問題が多くなる傾向にあるのだろう。

派閥に含まれるすべての議員が互いに知り合い同士 = すべてのノードが直接繋がっているような集合を考えればいい。だから間接的に繋がっているかどうかを見る必要はない。

あとはそのような集合の中でノード数が最も多い組み合わせを探索し、そのサイズを提示する。dfsが苦手なので全集合の列挙にはbit探索を使った。

おれが解けたんだからDの中では簡単な部類に入るんだと思う。

signed main() {
    int n, m; cin >> n >> m;
    int graph[12][12] = { 0 };
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y; x--, y--;
        graph[x][y] = 1; graph[y][x] = 1;
    }
 
    int ans = 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> as;
        for (int i = 0; i < n; i++) {
            if (1 & (mask >> i)) {
                as.push_back(i);
            }
        }
 
        bool ok = true;
        for (auto a : as) {
            for (auto b : as) {
                if (a == b) continue; // 同一ノードは無視
                if (graph[a][b] != 1) { // 直接繋がっていないノードを含む集合をはじく
                    ok = false;
                }
            }
        }
        if (ok) {
            ans = max(ans, (int)as.size());
        }
    }
    cout << ans << endl;
}