ABC 002 D

今日はこの問題を解きました。

abc002.contest.atcoder.jp

n人の知り合い関係が与えられます。全員が互いに知り合いのグループを作るとき、最大何人のグループができるでしょうか、という問題です。

今回nの最大値が12ということで、bitDPを用いました。また知り合い関係も接続行列で表せるのでとても楽。
回答はこんな感じです。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        int connection_matrix[12][12] = {};
        for(int i = 0; i < m; i++){
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            connection_matrix[x][y] = 1;
            connection_matrix[y][x] = 1;
        }
        int result[1 << 12] = {};
        int ans = 1;
        for(int i = 0; i < n; i++){
            result[1 << i] = 1;
        }
        for(int i = 0; i < 1 << n; i++){
            if(result[i] == 0) continue; // このような状態になることはないのでcontinueでとばす
            for(int j = 0; j < n; j++){
                if((1 << j & i) == 0){ // 現在見ている二進数について、jの位がまだ0(= j番目の人が加えられていない)
                    bool canadd = true; // j番目の人を足せるか？
                    for(int k = 0; k < n; k++){
                        if((1 << k & i) == 0) continue; // k番目の人が加えられてなかったらとばす
                        if(connection_matrix[j][k] == 0){ // j番目の人とk番目の人が知り合いではなかったら追加できない
                            canadd = false;
                            break;
                        }
                    }
                    if(canadd){
                        result[i | 1 << j] = result[i] + 1;
                        ans = max(ans, result[i | 1 << j]);
                    }
                }
            }
            // cout << i << " " << result[i] << endl;
        }
        cout << ans << endl;
        return 0;
    }

result[i]は、iを二進数にしたとき、1になっている位の人がグループに入っていることを示し、その値はグループの人数を表します。
現在のグループに一人追加することを考えます。
2^0~2^(n-1)の位の値を見ます。1であればすでにグループに入っているので飛ばします。
そうでないときは、その人を追加できるかチェックします。
再び2^0~2^(n-1)の位の値を見ます。すでにグループに入っている、つまり1になっているとき、その人がこれから追加しようとしている人と知り合いかチェック。もし知り合いでなかったら追加できないのでフラグ(canadd)をfalseにしておきます。
その後canaddがtrueであれば追加できるということなので、追加した場合のresultとansの値を更新します。
これを繰り返して答えを得ます。

最初xとyの値を1減らすのを忘れていたので答えが狂ってしまい焦りました。