彩色数を求めるアルゴリズム

code:cpp

int ChromaticNumber(const vector<vector<bool>> &tmpg) {

int n = tmpg.size();

if (n == 0) return 0;

vector<int> g(n);

for (int i = 0; i < n; i ++) {

for (int j = 0; j < n; j ++) {

}

}

}

int all = 1 << n;

vector<int> a(all), s(all);

int modulo = 998244353;

for (int i = 1; i < all; i ++) {

int j = __builtin_ctz(i);

}

for (int i = 0; i < all; i ++) {

}

for (int k = 1; k < n; k ++) {

long long sum = 0;

for (int i = 0; i < all; i ++) {

sum += cur;

}

if (sum % modulo != 0) return k;

}

return n;

}

しくみ：

使用例

vector<vector<bool>>には隣接リストが入っている。それを渡すことで、そのグラフの彩色数を求めることができる。