C++ Library for Competitive Programming
#include "emthrm/graph/chromatic_number.hpp"
隣接頂点間で色が異なるような頂点彩色に必要な最小の色の数である。
$O(2^{\lvert V \rvert} \lvert V \rvert)$
名前 | 戻り値 |
---|---|
template <typename CostType> int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph);
|
無向グラフ $\mathrm{graph}$ の彩色数 |
https://judge.yosupo.jp/submission/40942
#ifndef EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_
#define EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_
#include <bit>
#include <numeric>
#include <ranges>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph) {
const int n = graph.size();
std::vector<int> adj(n, 0);
for (int i = 0; i < n; ++i) {
for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
adj[i] |= 1 << e;
}
}
std::vector<int> indep(1 << n);
indep[0] = 1;
for (unsigned int i = 1; i < (1 << n); ++i) {
const int v = std::countr_zero(i);
indep[i] = indep[i ^ (1 << v)] + indep[(i ^ (1 << v)) & ~adj[v]];
}
int res = n;
for (const int mod : std::vector<int>{1000000007, 1000000011}) {
std::vector<long long> f(1 << n);
for (unsigned int i = 0; i < (1 << n); ++i) {
f[i] = ((n - std::popcount(i)) & 1 ? mod - 1 : 1);
}
for (int c = 1; c < res; ++c) {
for (int i = 0; i < (1 << n); ++i) {
f[i] = (f[i] * indep[i]) % mod;
}
if (std::reduce(f.begin(), f.end(), 0LL) % mod > 0) {
res = c;
break;
}
}
}
return res;
}
} // namespace emthrm
#endif // EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_
#line 1 "include/emthrm/graph/chromatic_number.hpp"
#include <bit>
#include <numeric>
#include <ranges>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/chromatic_number.hpp"
namespace emthrm {
template <typename CostType>
int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph) {
const int n = graph.size();
std::vector<int> adj(n, 0);
for (int i = 0; i < n; ++i) {
for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
adj[i] |= 1 << e;
}
}
std::vector<int> indep(1 << n);
indep[0] = 1;
for (unsigned int i = 1; i < (1 << n); ++i) {
const int v = std::countr_zero(i);
indep[i] = indep[i ^ (1 << v)] + indep[(i ^ (1 << v)) & ~adj[v]];
}
int res = n;
for (const int mod : std::vector<int>{1000000007, 1000000011}) {
std::vector<long long> f(1 << n);
for (unsigned int i = 0; i < (1 << n); ++i) {
f[i] = ((n - std::popcount(i)) & 1 ? mod - 1 : 1);
}
for (int c = 1; c < res; ++c) {
for (int i = 0; i < (1 << n); ++i) {
f[i] = (f[i] * indep[i]) % mod;
}
if (std::reduce(f.begin(), f.end(), 0LL) % mod > 0) {
res = c;
break;
}
}
}
return res;
}
} // namespace emthrm