ABC002: D - 派閥

問題

D - 派閥

解説

派閥に含まれる人たちは互いに知り合いである必要がある。知り合いの関係は行の入力で与えられている。 最大の派閥となる集合をBit全探索し、2重ループで関係性をチェックする。なのでは十分間に合う。

int main() {
  int N, M; cin >> N >> M;
  bool rel[12][12] = {};
  rep(i, M) {
    int x, y; cin >> x >> y; x--, y--;
    rel[x][y] = rel[y][x] = 1;
  }
  int ans = 1;
  rep(S, (1<<N)) {
    bool good = 1;
    rep(i, N) {
      if (S >> i & 1) {
        bool ok = 1;
        rep(j, N) if (S >> j & 1) {
          if (i != j && !rel[i][j]) {
            ok = 0;
            break;
          }
        }
        if (!ok) {
          good = 0;
          break;
        }
      }
    }
    if (good) {
      maximize(ans, __builtin_popcount(S));
    }
  }
  cout << ans << endl;
}