Submission #112172

---

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 = 1; i <= N; i++){
    if( val >> i & 1 ) cnt++;
  }
  return cnt;
}

int check_count(int index){
  int val = human_list[index];
  int n_val;
  int max_cnt = 0;
  int min_cnt = 12;
  vector<int> val_list(MAX_N+1, 0);
  map<int, int> cnt_list;

  for(int i = 1; i <= N; i++){
    if( val >> i & 1 ){
      val_list[i]++;
    }
  }

  for(int i = 1; i <= N; i++){
    if( i != index && val >> i & 1 ){
      n_val = human_list[i];

      for(int j = 1; j <= N; j++){
        if( n_val >> j & 1 ){
          val_list[j]++;
        }
      }
    }
  }

  for(int i = 1; i <= N; i++){
    if(val_list[i] != 0){
      for(int j = val_list[i]; j > 0; j--){
        cnt_list[j]++;
      }
    }
  }

  /*
  for(int i = 1; i <= N; i++){
    cout << val_list[i] << " ";
  }
  cout << endl;
  */

  map<int,int>::iterator it = cnt_list.begin();

  while( it != cnt_list.end() ){
    if( (*it).first == (*it).second ){
      max_cnt = max( max_cnt, (*it).second );
    }
    it++;
  }

  return max_cnt;
  //return min_cnt;
}

int main(){
  cin >> N >> M;
  int max_cnt = 0;
  int a, b;
  vector<bool> node_flag(N, false);

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

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

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

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

  for(int i = 1; i <= N; i++){
    if( node_flag[i]){
      max_cnt = max( max_cnt, check_count(i));
    }
  }

  cout << max_cnt << endl;
}

Submission Info

Judge Result