Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:heavy_check_mark: Chromatic Number(彩色数)
(graph/others/chromatic-number.hpp)

概要

グラフの彩色数を求める. 彩色数とは, 隣接する頂点が異なる色となるように彩色するために必要な最小色数である.

あるグラフが $k$ 彩色可能であることと, $k$ 個の独立集合で被覆できることは必要十分条件である. つまり独立集合から $k$ 個の頂点を選んで被覆する方法の総数が求まれば良い. これはbit DPと包除原理を用いて効率的に求められる.

使い方

計算量

Verified with

Code

#pragma once

/**
 * @brief Chromatic Number(彩色数)
 * @docs docs/chromatic-number.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */
template< typename Matrix >
int chromatic_number(Matrix &g) {
  int N = (int) g.size();
  vector< int > es(N);
  for(int i = 0; i < (int) g.size(); i++) {
    for(int j = 0; j < (int) g.size(); j++) {
      if(g[i][j] != 0) es[i] |= 1 << j;
    }
  }
  vector< int > ind(1 << N);
  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]];
  }
  vector< int > cnt((1 << N) + 1);
  for(int i = 0; i < (1 << N); i++) {
    cnt[ind[i]] += __builtin_parity(i) ? -1 : 1;
  }
  vector< pair< unsigned, int > > hist;
  for(int i = 1; i <= (1 << N); i++) {
    if(cnt[i]) hist.emplace_back(i, cnt[i]);
  }
  constexpr int mods[] = {1000000007, 1000000011, 1000000021};
  int ret = N;
  for(int k = 0; k < 3; k++) {
    auto buf = hist;
    for(int c = 1; c < ret; c++) {
      int64_t sum = 0;
      for(auto&[i, x] : buf) {
        sum += (x = int64_t(x) * i % mods[k]);
      }
      if(sum % mods[k]) ret = c;
    }
  }
  return ret;
}
#line 2 "graph/others/chromatic-number.hpp"

/**
 * @brief Chromatic Number(彩色数)
 * @docs docs/chromatic-number.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */
template< typename Matrix >
int chromatic_number(Matrix &g) {
  int N = (int) g.size();
  vector< int > es(N);
  for(int i = 0; i < (int) g.size(); i++) {
    for(int j = 0; j < (int) g.size(); j++) {
      if(g[i][j] != 0) es[i] |= 1 << j;
    }
  }
  vector< int > ind(1 << N);
  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]];
  }
  vector< int > cnt((1 << N) + 1);
  for(int i = 0; i < (1 << N); i++) {
    cnt[ind[i]] += __builtin_parity(i) ? -1 : 1;
  }
  vector< pair< unsigned, int > > hist;
  for(int i = 1; i <= (1 << N); i++) {
    if(cnt[i]) hist.emplace_back(i, cnt[i]);
  }
  constexpr int mods[] = {1000000007, 1000000011, 1000000021};
  int ret = N;
  for(int k = 0; k < 3; k++) {
    auto buf = hist;
    for(int c = 1; c < ret; c++) {
      int64_t sum = 0;
      for(auto&[i, x] : buf) {
        sum += (x = int64_t(x) * i % mods[k]);
      }
      if(sum % mods[k]) ret = c;
    }
  }
  return ret;
}
Back to top page