maximum_clique.hpp¶
精确求至多 64 点无向图的最大团或最大独立集；返回任意最优顶点集合，忽略自环和重边。使用补图分块、位集与贪心着色剪枝，最坏仍为指数级。
Complexity: Time: \(O(n 2^{n} + m)\) worst-case upper bound, \(n \le 64\). Space: \(O(n^{2})\) peak coloring state, including \(O(n)\) recursion depth.
AC 记录：maximum_independent_set。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n 2^n + m) worst-case upper bound, n <= 64.
/// Space: O(n^2) peak coloring state, including O(n) recursion depth.
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
namespace maximum_clique_internal {
inline std::vector<int>
solve(int n, const std::vector<std::pair<int, int>> &es, bool independent) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
std::vector<mask> g(n);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
g[u] |= mask(1) << v;
g[v] |= mask(1) << u;
}
}
if (independent)
for (int u = 0; u < n; ++u) g[u] = all & ~(g[u] | (mask(1) << u));
std::vector<int> best, current, answer;
best.reserve(n);
current.reserve(n);
answer.reserve(n);
auto dfs = [&](auto &self, mask can) -> void {
if (!can) {
if (current.size() > best.size()) best = current;
return;
}
int count = std::popcount(can);
if (current.size() + std::size_t(count) <= best.size()) return;
std::vector<std::pair<int, int>> order;
order.reserve(count);
mask remaining = can;
for (int color = 1; remaining; ++color) {
mask available = remaining;
while (available) {
int u = std::countr_zero(available);
mask bit = mask(1) << u;
remaining &= ~bit;
available &= ~(g[u] | bit);
order.emplace_back(u, color);
}
}
for (int i = int(order.size()) - 1; i >= 0; --i) {
auto [u, color] = order[i];
if (current.size() + std::size_t(color) <= best.size()) return;
current.push_back(u);
self(self, can & g[u]);
current.pop_back();
can &= ~(mask(1) << u);
}
};
// Different connected components of the complement are completely joined
// in g, so their maximum cliques can be solved separately and combined.
mask remaining = all;
while (remaining) {
mask part = remaining & -remaining, todo = part;
remaining ^= part;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
mask next = remaining & ~g[u];
remaining ^= next;
todo |= next;
part |= next;
}
best.clear();
dfs(dfs, part);
answer.insert(answer.end(), best.begin(), best.end());
}
return answer;
}
} // namespace maximum_clique_internal
/// @brief Return any maximum clique for n <= 64 using greedy-color bounds.
/// Ignore loops and duplicate edges. Vertex order and tie choices are unspecified.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, false);
}
/// @brief Return any maximum independent set for n <= 64, ignoring loops and
/// duplicate edges. Complement the adjacency masks without forming an edge list.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, true);
}
} // namespace noya
// NOYA_MAXIMUM_CLIQUE_HPP
#ifndef NOYA_MAXIMUM_CLIQUE_HPP
#define NOYA_MAXIMUM_CLIQUE_HPP 1
/// @complexity Time: O(n 2^n + m) worst-case upper bound, n <= 64.
/// Space: O(n^2) peak coloring state, including O(n) recursion depth.
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
namespace maximum_clique_internal {
inline std::vector<int>
solve(int n, const std::vector<std::pair<int, int>> &es, bool independent) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
std::vector<mask> g(n);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
g[u] |= mask(1) << v;
g[v] |= mask(1) << u;
}
}
if (independent)
for (int u = 0; u < n; ++u) g[u] = all & ~(g[u] | (mask(1) << u));
std::vector<int> best, current, answer;
best.reserve(n);
current.reserve(n);
answer.reserve(n);
auto dfs = [&](auto &self, mask can) -> void {
if (!can) {
if (current.size() > best.size()) best = current;
return;
}
int count = std::popcount(can);
if (current.size() + std::size_t(count) <= best.size()) return;
std::vector<std::pair<int, int>> order;
order.reserve(count);
mask remaining = can;
for (int color = 1; remaining; ++color) {
mask available = remaining;
while (available) {
int u = std::countr_zero(available);
mask bit = mask(1) << u;
remaining &= ~bit;
available &= ~(g[u] | bit);
order.emplace_back(u, color);
}
}
for (int i = int(order.size()) - 1; i >= 0; --i) {
auto [u, color] = order[i];
if (current.size() + std::size_t(color) <= best.size()) return;
current.push_back(u);
self(self, can & g[u]);
current.pop_back();
can &= ~(mask(1) << u);
}
};
// Different connected components of the complement are completely joined
// in g, so their maximum cliques can be solved separately and combined.
mask remaining = all;
while (remaining) {
mask part = remaining & -remaining, todo = part;
remaining ^= part;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
mask next = remaining & ~g[u];
remaining ^= next;
todo |= next;
part |= next;
}
best.clear();
dfs(dfs, part);
answer.insert(answer.end(), best.begin(), best.end());
}
return answer;
}
} // namespace maximum_clique_internal
/// @brief Return any maximum clique for n <= 64 using greedy-color bounds.
/// Ignore loops and duplicate edges. Vertex order and tie choices are unspecified.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, false);
}
/// @brief Return any maximum independent set for n <= 64, ignoring loops and
/// duplicate edges. Complement the adjacency masks without forming an edge list.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, true);
}
} // namespace noya
#endif // NOYA_MAXIMUM_CLIQUE_HPP
/// @complexity Time: O(n 2^n + m) worst-case upper bound, n <= 64.
/// Space: O(n^2) peak coloring state, including O(n) recursion depth.
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
namespace maximum_clique_internal {
inline std::vector<int>
solve(int n, const std::vector<std::pair<int, int>> &es, bool independent) {
assert(0 <= n && n <= 64);
using mask = std::uint64_t;
mask all = n == 64 ? ~mask(0) : (mask(1) << n) - 1;
std::vector<mask> g(n);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
g[u] |= mask(1) << v;
g[v] |= mask(1) << u;
}
}
if (independent)
for (int u = 0; u < n; ++u) g[u] = all & ~(g[u] | (mask(1) << u));
std::vector<int> best, current, answer;
best.reserve(n);
current.reserve(n);
answer.reserve(n);
auto dfs = [&](auto &self, mask can) -> void {
if (!can) {
if (current.size() > best.size()) best = current;
return;
}
int count = std::popcount(can);
if (current.size() + std::size_t(count) <= best.size()) return;
std::vector<std::pair<int, int>> order;
order.reserve(count);
mask remaining = can;
for (int color = 1; remaining; ++color) {
mask available = remaining;
while (available) {
int u = std::countr_zero(available);
mask bit = mask(1) << u;
remaining &= ~bit;
available &= ~(g[u] | bit);
order.emplace_back(u, color);
}
}
for (int i = int(order.size()) - 1; i >= 0; --i) {
auto [u, color] = order[i];
if (current.size() + std::size_t(color) <= best.size()) return;
current.push_back(u);
self(self, can & g[u]);
current.pop_back();
can &= ~(mask(1) << u);
}
};
// Different connected components of the complement are completely joined
// in g, so their maximum cliques can be solved separately and combined.
mask remaining = all;
while (remaining) {
mask part = remaining & -remaining, todo = part;
remaining ^= part;
while (todo) {
int u = std::countr_zero(todo);
todo &= todo - 1;
mask next = remaining & ~g[u];
remaining ^= next;
todo |= next;
part |= next;
}
best.clear();
dfs(dfs, part);
answer.insert(answer.end(), best.begin(), best.end());
}
return answer;
}
} // namespace maximum_clique_internal
/// @brief Return any maximum clique for n <= 64 using greedy-color bounds.
/// Ignore loops and duplicate edges. Vertex order and tie choices are unspecified.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, false);
}
/// @brief Return any maximum independent set for n <= 64, ignoring loops and
/// duplicate edges. Complement the adjacency masks without forming an edge list.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
return maximum_clique_internal::solve(n, es, true);
}
} // namespace noya
// NOYA_MAXIMUM_CLIQUE_HPP