chromatic_number.hpp¶
精确计算至多 64 点的最小顶点着色；分连通块进行 DSATUR 搜索，增量维护禁色并用贪心团剪枝。忽略自环、归一化重边，最坏仍为指数级。
Complexity: Time: \(O(m + n^{2} + n T)\), where \(T\) is the number of visited search states (exponential worst case). Space: \(O(n)\), including recursion.
AC 记录：chromatic_number。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(m + n^2 + n T), where T is the number of visited
/// search states (exponential worst case). Space: O(n), including recursion.
#include <algorithm>
#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 0 <= n <= 64 by DSATUR
/// branch-and-bound. Ignore loops and duplicate edges; leave es unchanged.
/// Return colors in [0,k), with no canonical choice of optimal coloring.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
std::vector<mask> g(n), ban(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a] |= mask(1) << b;
g[b] |= mask(1) << a;
}
}
std::vector<int> deg(n), col(n);
for (int u = 0; u < n; ++u) deg[u] = std::popcount(g[u]);
auto select = [&](mask rem) {
int sel = -1, cs = -1, cd = -1;
for (; rem; rem &= rem - 1) {
int u = std::countr_zero(rem), sat = std::popcount(ban[u]);
if (sat > cs || (sat == cs && deg[u] > cd)) {
sel = u;
cs = sat;
cd = deg[u];
}
}
return sel;
};
graph_coloring_result bst{0, std::vector<int>(n)};
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
while (all) {
// Solve components independently, reusing color names across components.
mask comp = 0, todo = all & -all;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
comp |= mask(1) << u;
todo |= g[u] & ~comp;
}
all &= ~comp;
int upper = 0, lower = 0;
for (mask rem = comp; rem; rem &= rem - 1)
bst.col[std::countr_zero(rem)] = upper++;
// All bans are zero here: select constructs a degree-greedy clique.
for (mask rem = comp; rem; ++lower) rem &= g[select(rem)];
auto dfs = [&](auto &self, mask rem, int used) -> void {
if (used >= upper || upper == lower) return;
if (!rem) {
upper = used;
for (mask rest = comp; rest; rest &= rest - 1) {
int u = std::countr_zero(rest);
bst.col[u] = col[u];
}
return;
}
int u = select(rem);
rem ^= mask(1) << u;
// Only existing colors and the first new color are distinct choices.
// We seek fewer than upper <= 64 colors, so limit is at most 63.
int limit = std::min(used + 1, upper - 1);
mask avail = ((mask(1) << limit) - 1) & ~ban[u];
while (avail && upper > lower) {
int c = std::countr_zero(avail);
avail &= avail - 1;
if (c + 1 >= upper) break;
mask bit = mask(1) << c, changed = 0;
for (mask adj = g[u] & rem; adj; adj &= adj - 1) {
int v = std::countr_zero(adj);
if (!(ban[v] & bit)) {
ban[v] |= bit;
changed |= mask(1) << v;
}
}
col[u] = c;
self(self, rem, std::max(used, c + 1));
// Clear only bits introduced here: another neighbor may use c too.
for (; changed; changed &= changed - 1)
ban[std::countr_zero(changed)] ^= bit;
}
};
dfs(dfs, comp, 0);
bst.k = std::max(bst.k, upper);
}
return bst;
}
} // namespace noya
// NOYA_CHROMATIC_NUMBER_HPP
#ifndef NOYA_CHROMATIC_NUMBER_HPP
#define NOYA_CHROMATIC_NUMBER_HPP 1
/// @complexity Time: O(m + n^2 + n T), where T is the number of visited
/// search states (exponential worst case). Space: O(n), including recursion.
#include <algorithm>
#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 0 <= n <= 64 by DSATUR
/// branch-and-bound. Ignore loops and duplicate edges; leave es unchanged.
/// Return colors in [0,k), with no canonical choice of optimal coloring.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
std::vector<mask> g(n), ban(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a] |= mask(1) << b;
g[b] |= mask(1) << a;
}
}
std::vector<int> deg(n), col(n);
for (int u = 0; u < n; ++u) deg[u] = std::popcount(g[u]);
auto select = [&](mask rem) {
int sel = -1, cs = -1, cd = -1;
for (; rem; rem &= rem - 1) {
int u = std::countr_zero(rem), sat = std::popcount(ban[u]);
if (sat > cs || (sat == cs && deg[u] > cd)) {
sel = u;
cs = sat;
cd = deg[u];
}
}
return sel;
};
graph_coloring_result bst{0, std::vector<int>(n)};
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
while (all) {
// Solve components independently, reusing color names across components.
mask comp = 0, todo = all & -all;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
comp |= mask(1) << u;
todo |= g[u] & ~comp;
}
all &= ~comp;
int upper = 0, lower = 0;
for (mask rem = comp; rem; rem &= rem - 1)
bst.col[std::countr_zero(rem)] = upper++;
// All bans are zero here: select constructs a degree-greedy clique.
for (mask rem = comp; rem; ++lower) rem &= g[select(rem)];
auto dfs = [&](auto &self, mask rem, int used) -> void {
if (used >= upper || upper == lower) return;
if (!rem) {
upper = used;
for (mask rest = comp; rest; rest &= rest - 1) {
int u = std::countr_zero(rest);
bst.col[u] = col[u];
}
return;
}
int u = select(rem);
rem ^= mask(1) << u;
// Only existing colors and the first new color are distinct choices.
// We seek fewer than upper <= 64 colors, so limit is at most 63.
int limit = std::min(used + 1, upper - 1);
mask avail = ((mask(1) << limit) - 1) & ~ban[u];
while (avail && upper > lower) {
int c = std::countr_zero(avail);
avail &= avail - 1;
if (c + 1 >= upper) break;
mask bit = mask(1) << c, changed = 0;
for (mask adj = g[u] & rem; adj; adj &= adj - 1) {
int v = std::countr_zero(adj);
if (!(ban[v] & bit)) {
ban[v] |= bit;
changed |= mask(1) << v;
}
}
col[u] = c;
self(self, rem, std::max(used, c + 1));
// Clear only bits introduced here: another neighbor may use c too.
for (; changed; changed &= changed - 1)
ban[std::countr_zero(changed)] ^= bit;
}
};
dfs(dfs, comp, 0);
bst.k = std::max(bst.k, upper);
}
return bst;
}
} // namespace noya
#endif // NOYA_CHROMATIC_NUMBER_HPP
/// @complexity Time: O(m + n^2 + n T), where T is the number of visited
/// search states (exponential worst case). Space: O(n), including recursion.
#include <algorithm>
#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 0 <= n <= 64 by DSATUR
/// branch-and-bound. Ignore loops and duplicate edges; leave es unchanged.
/// Return colors in [0,k), with no canonical choice of optimal coloring.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
std::vector<mask> g(n), ban(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a] |= mask(1) << b;
g[b] |= mask(1) << a;
}
}
std::vector<int> deg(n), col(n);
for (int u = 0; u < n; ++u) deg[u] = std::popcount(g[u]);
auto select = [&](mask rem) {
int sel = -1, cs = -1, cd = -1;
for (; rem; rem &= rem - 1) {
int u = std::countr_zero(rem), sat = std::popcount(ban[u]);
if (sat > cs || (sat == cs && deg[u] > cd)) {
sel = u;
cs = sat;
cd = deg[u];
}
}
return sel;
};
graph_coloring_result bst{0, std::vector<int>(n)};
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
while (all) {
// Solve components independently, reusing color names across components.
mask comp = 0, todo = all & -all;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
comp |= mask(1) << u;
todo |= g[u] & ~comp;
}
all &= ~comp;
int upper = 0, lower = 0;
for (mask rem = comp; rem; rem &= rem - 1)
bst.col[std::countr_zero(rem)] = upper++;
// All bans are zero here: select constructs a degree-greedy clique.
for (mask rem = comp; rem; ++lower) rem &= g[select(rem)];
auto dfs = [&](auto &self, mask rem, int used) -> void {
if (used >= upper || upper == lower) return;
if (!rem) {
upper = used;
for (mask rest = comp; rest; rest &= rest - 1) {
int u = std::countr_zero(rest);
bst.col[u] = col[u];
}
return;
}
int u = select(rem);
rem ^= mask(1) << u;
// Only existing colors and the first new color are distinct choices.
// We seek fewer than upper <= 64 colors, so limit is at most 63.
int limit = std::min(used + 1, upper - 1);
mask avail = ((mask(1) << limit) - 1) & ~ban[u];
while (avail && upper > lower) {
int c = std::countr_zero(avail);
avail &= avail - 1;
if (c + 1 >= upper) break;
mask bit = mask(1) << c, changed = 0;
for (mask adj = g[u] & rem; adj; adj &= adj - 1) {
int v = std::countr_zero(adj);
if (!(ban[v] & bit)) {
ban[v] |= bit;
changed |= mask(1) << v;
}
}
col[u] = c;
self(self, rem, std::max(used, c + 1));
// Clear only bits introduced here: another neighbor may use c too.
for (; changed; changed &= changed - 1)
ban[std::countr_zero(changed)] ^= bit;
}
};
dfs(dfs, comp, 0);
bst.k = std::max(bst.k, upper);
}
return bst;
}
} // namespace noya
// NOYA_CHROMATIC_NUMBER_HPP