Submission #20064900

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}

int n, m;
ll dist[12][12];

int popc(int bm)
{
  int r = 0;
  while (bm != 0){
    if (bm&1) r++;
    bm >>= 1;
  }
  return r;
}

bool check(int bm){
  for (int i = 0; i < n - 1; i++){
    for (int j = i+1; j < n; j++){
      if (((1 << i) & bm) && ((1 << j) & bm) && dist[i][j] > 1)
	return false;
    }
  }
  return true;
}

int main()
{
  cin >> n >> m;

  for (int i = 0; i < 12; i++)
    for (int j = 0; j < 12; j++)
      dist[i][j] = INF;

  vector<vector<int>> edges(n);

  for (int i = 0; i < m; i++){
    int x, y;
    cin >> x >> y; x--; y--;
    dist[x][y] = dist[y][x] = 1;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }

  for (int k = 0; k < n; k++){
    for (int i = 0; i < n; i++){
      for (int j = 0; j < n; j++){
	chmin(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  
  int ans = 0;
  for (int bm = (1 << n) - 1; bm > 0; bm--){
    if (check(bm)){
      ans = max(ans, popc(bm));
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result