Submission #112206

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int MAX_N = 12;
int N, M;
int human_list[MAX_N+1];

int count_human(int val){
  int cnt = 0;
  for(int i = 0; i < N; i++){
    if( val >> i & 1 ) cnt++;
  }
  return cnt;
}

int main(){
  cin >> N >> M;
  int max_cnt = 0;
  int a, b;

  if( M == 0 ){
    cout << 1 << endl;
    return 0;
  }

  for(int i = 0; i < N; i++){
    human_list[i] |= (1 << i);
  }


  for(int i = 0; i < M; i++){
    cin >> a >> b;

    human_list[a-1] |= (1 << (b-1));
    human_list[b-1] |= (1 << (a-1));
  }

  for(int i = 1; i < (1 << N); i++){
    bool flag = true;
    for(int j = 0; j < N; j++){
      if( (i >> j & 1) && i != (i & human_list[j]) ) flag = false;
    }
    if( flag ) max_cnt = max( max_cnt, count_human(i) );
  }

  cout << max_cnt << endl;
}

Submission Info

Judge Result