This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/others/chromatic-number.hpp"
グラフの彩色数を求める. 彩色数とは, 隣接する頂点が異なる色となるように彩色するために必要な最小色数である.
あるグラフが $k$ 彩色可能であることと, $k$ 個の独立集合で被覆できることは必要十分条件である. つまり独立集合から $k$ 個の頂点を選んで被覆する方法の総数が求まれば良い. これはbit DPと包除原理を用いて効率的に求められる.
chromatic_number(g)
: 隣接行列 g
で表されるグラフの彩色数を求める.#pragma once
/**
* @brief Chromatic Number(彩色数)
*
* @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(彩色数)
*
* @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;
}