彩色数

• グラフの彩色数問題とは、辺で結ばれた頂点は違う色で塗る時、最低何色必要かという問題
• ei1333さんのライブラリを（引数を変更して）使いました記念
  • https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html
  • 計算量O(2^N N)
• AC https://atcoder.jp/contests/abc187/submissions/19173908

// 天から「補グラフの彩色数だよ」と言われた場合の解法
 
int chromatic_number(vector<vector<bool>> g) {
  int N = (int) g.size();
  vector< int > es(N);
  for(int i = 0; i < g.size(); i++) {
    for(int j = 0; j < g.size(); j++) {
      es[i] |= g[i][j] << j;
    }
  }
  int ret = N;
  for(int d : {7, 11, 21}) {
    int mod = 1e9 + d;
    vector< int > ind(1 << N), aux(1 << N, 1);
    ind[0] = 1;
    for(int S = 1; S < 1 << N; S++) {
      int u = __builtin_ctz(S);
      ind[S] = ind[S ^ (1 << u)] + ind[(S ^ (1 << u)) & ~es[u]];
    }
    for(int i = 1; i < ret; i++) {
      int64_t all = 0;
      for(int j = 0; j < 1 << N; j++) {
        int S = j ^(j >> 1);
        aux[S] = (1LL * aux[S] * ind[S]) % mod;
        all += j & 1 ? aux[S] : mod - aux[S];
      }
      if(all % mod) ret = i;
    }
  }
  return ret;
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N,M;
    cin>>N>>M;
 
    vector<vector<bool>> A(N, vector<bool>(N));
    rep(i,M){
      ll a,b;cin>>a>>b;
      a--;b--;
      A[a][b]=true;
      A[b][a]=true;
    }
    // 補グラフにする
    rep(i,N){
      rep(j,N){
        A[i][j] = 1-A[i][j];
      }
    }
 
    ll ans = chromatic_number(A);
    p(ans);
   
    return 0;
}