chromatic_number.hpp¶
精确计算一般图的最小顶点着色数；适合点数较小的不可相邻同色分组。
Complexity: Time: O(n 2^n). Space: O(2^n).
AC 记录：chromatic_number。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n 2^n).
/// Space: O(2^n).
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
struct graph_coloring_result {
int k = 0;
std::vector<int> col;
};
/// @brief Exact minimum vertex coloring for an undirected graph with at most
/// 64 vertices using DSATUR branch-and-bound.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
std::vector<std::uint64_t> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a == b) {
continue;
}
g[a] |= std::uint64_t(1) << b;
g[b] |= std::uint64_t(1) << a;
}
graph_coloring_result bst;
bst.k = n;
bst.col.resize(n);
for (int u = 0; u < n; u++) {
bst.col[u] = u;
}
if (n == 0) {
return bst;
}
std::vector<int> col(n, -1);
auto dfs = [&](auto &self, int cnt, int uc) -> void {
if (uc >= bst.k) {
return;
}
if (cnt == n) {
bst.k = uc;
bst.col = col;
return;
}
int sel = -1;
int cs = -1;
int cd = -1;
std::uint64_t cf = 0;
for (int u = 0; u < n; u++) {
if (col[u] != -1) {
continue;
}
std::uint64_t ban = 0;
std::uint64_t adj = g[u];
while (adj != 0) {
int nxt = std::countr_zero(adj);
adj &= adj - 1;
if (col[nxt] != -1) {
ban |= std::uint64_t(1) << col[nxt];
}
}
int sat = std::popcount(ban);
int deg = std::popcount(g[u]);
if (sat > cs || (sat == cs && deg > cd)) {
sel = u;
cs = sat;
cd = deg;
cf = ban;
}
}
for (int val = 0; val < uc; val++) {
if (!(cf >> val & 1)) {
col[sel] = val;
self(self, cnt + 1, uc);
col[sel] = -1;
}
}
if (uc + 1 < bst.k) {
col[sel] = uc;
self(self, cnt + 1, uc + 1);
col[sel] = -1;
}
};
dfs(dfs, 0, 0);
return bst;
}
} // namespace noya
#ifndef NOYA_CHROMATIC_NUMBER_HPP
#define NOYA_CHROMATIC_NUMBER_HPP 1
/// @complexity Time: O(n 2^n).
/// Space: O(2^n).
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
struct graph_coloring_result {
int k = 0;
std::vector<int> col;
};
/// @brief Exact minimum vertex coloring for an undirected graph with at most
/// 64 vertices using DSATUR branch-and-bound.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
std::vector<std::uint64_t> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a == b) {
continue;
}
g[a] |= std::uint64_t(1) << b;
g[b] |= std::uint64_t(1) << a;
}
graph_coloring_result bst;
bst.k = n;
bst.col.resize(n);
for (int u = 0; u < n; u++) {
bst.col[u] = u;
}
if (n == 0) {
return bst;
}
std::vector<int> col(n, -1);
auto dfs = [&](auto &self, int cnt, int uc) -> void {
if (uc >= bst.k) {
return;
}
if (cnt == n) {
bst.k = uc;
bst.col = col;
return;
}
int sel = -1;
int cs = -1;
int cd = -1;
std::uint64_t cf = 0;
for (int u = 0; u < n; u++) {
if (col[u] != -1) {
continue;
}
std::uint64_t ban = 0;
std::uint64_t adj = g[u];
while (adj != 0) {
int nxt = std::countr_zero(adj);
adj &= adj - 1;
if (col[nxt] != -1) {
ban |= std::uint64_t(1) << col[nxt];
}
}
int sat = std::popcount(ban);
int deg = std::popcount(g[u]);
if (sat > cs || (sat == cs && deg > cd)) {
sel = u;
cs = sat;
cd = deg;
cf = ban;
}
}
for (int val = 0; val < uc; val++) {
if (!(cf >> val & 1)) {
col[sel] = val;
self(self, cnt + 1, uc);
col[sel] = -1;
}
}
if (uc + 1 < bst.k) {
col[sel] = uc;
self(self, cnt + 1, uc + 1);
col[sel] = -1;
}
};
dfs(dfs, 0, 0);
return bst;
}
} // namespace noya
#endif // NOYA_CHROMATIC_NUMBER_HPP
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
/// @complexity Time: O(n 2^n).
/// Space: O(2^n).
namespace noya {
struct graph_coloring_result {
int k = 0;
std::vector<int> col;
};
/// @brief Exact minimum vertex coloring for an undirected graph with at most
/// 64 vertices using DSATUR branch-and-bound.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
std::vector<std::uint64_t> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a == b) {
continue;
}
g[a] |= std::uint64_t(1) << b;
g[b] |= std::uint64_t(1) << a;
}
graph_coloring_result bst;
bst.k = n;
bst.col.resize(n);
for (int u = 0; u < n; u++) {
bst.col[u] = u;
}
if (n == 0) {
return bst;
}
std::vector<int> col(n, -1);
auto dfs = [&](auto &self, int cnt, int uc) -> void {
if (uc >= bst.k) {
return;
}
if (cnt == n) {
bst.k = uc;
bst.col = col;
return;
}
int sel = -1;
int cs = -1;
int cd = -1;
std::uint64_t cf = 0;
for (int u = 0; u < n; u++) {
if (col[u] != -1) {
continue;
}
std::uint64_t ban = 0;
std::uint64_t adj = g[u];
while (adj != 0) {
int nxt = std::countr_zero(adj);
adj &= adj - 1;
if (col[nxt] != -1) {
ban |= std::uint64_t(1) << col[nxt];
}
}
int sat = std::popcount(ban);
int deg = std::popcount(g[u]);
if (sat > cs || (sat == cs && deg > cd)) {
sel = u;
cs = sat;
cd = deg;
cf = ban;
}
}
for (int val = 0; val < uc; val++) {
if (!(cf >> val & 1)) {
col[sel] = val;
self(self, cnt + 1, uc);
col[sel] = -1;
}
}
if (uc + 1 < bst.k) {
col[sel] = uc;
self(self, cnt + 1, uc + 1);
col[sel] = -1;
}
};
dfs(dfs, 0, 0);
return bst;
}
} // namespace noya