D - 派閥

コメント歓迎です。
今回もビット全探索を使います。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

beta.atcoder.jp

方針

この問題では、派閥を作れる組み合わせをどのようにして求めるかがポイントとなります。

今回は最大人数が12人であり、全員に対して派閥に入るか入らないかの2択をビット全探索します。
そのため、最大でも通りの計算量で済みます。

今回新しく2次元配列を使いました。(ベクターの2次元配列は宣言の文法がわかりづらいですね。)

入力の情報から知り合いの場合、「1番さんから見て2番さんは知り合い」で、
「2番さんから見て1番さんも知り合い」といった形で情報をベクターに記録しておきます。

派閥が作れる条件としては、派閥に入れようとしている人(ビット全探索の"1")全員が、知り合いであればOKです。

逆に考えると、派閥に入れようとしている人で知り合いでない組み合わせがひとつでもあれば、
そのメンバーでは派閥は作れないことになります。

下のコードでは、そのような実装になっています。

コード(AC)

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int main(){
  // 入力
  int N, M;
  cin >> N >> M;

  // 2次元ベクター
  vector<vector<int> > relation(N, vector<int> (N, 0));

  // 知り合い関係を配列に記録
  int x, y;
  for (int i = 0; i < M; i++) {
    cin >> x >> y;
    relation[x-1][y-1] = relation[y-1][x-1] = 1;
  }

  // 答えの最小値は1
  int ans = 1;

  // ビット全探索 2^N
  for (int mask = 0; mask < (1 << N); mask++) {
    int factions = bitset<32>(mask).count();
    // 派閥メンバー数が解答として保持している値よりも少ない場合は処理をスキップ
    if (factions < ans) {
      continue;
    }
    // そのメンバーで派閥が組めるか判定
    bool judge = true;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < i; j++) {
        // 選択したメンバーで知り合いでない場合があったらNG判定
        if (mask >> i & mask >> j & 1 && !relation[i][j]) {
          judge = false;
        }
      }
    }
    // 条件を満たしたらansに代入
    if (judge) {
      ans = factions;
    }
  }

  // 出力
  cout << ans << endl;
}