Submission #111733

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define all(a) (a).begin(),(a).end()

int N, M;
bool relation[20][20];

int numofbits(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
  while (cin >> N >> M) {
    rep(i,N) rep(j,N) relation[i][j] = relation[j][i] = false;
    rep(i,M) {
      int x,y;
      cin >> x >> y;
      --x; --y;
      relation[x][y] = relation[y][x] = true;
    }

    int ans = 1;
    for (int S = 0; S < (1 << N); ++S) {
      int bit = numofbits(S);
      if (bit <= ans) continue;
      bool ok = true;      
      for (int i = 0; (i < N) && ok; ++i) {
        if (!(S >> i & 1)) continue;
        for (int j = 0; j < N; ++j) {
          if (i == j) continue;
          if (!(S >> j & 1)) continue;
          if (!relation[i][j]) {
            ok = false;
            break;
          }
        }
      }
      if (ok) {
        ans = bit;
      }      
    }

    printf("%d\n", ans);
  }
  return 0;
}

Submission Info

Judge Result