clique_enumeration.hpp¶
枚举无向图的所有团，并把每个团交给回调统计或计算贡献。
Complexity: Time: O((n + C) ceil(n / 64)) after O(n + m) graph construction, where C is the number of cliques. Space: O(n^2 / 64) g bits and O(n^2 / 64) recursion workspace.
AC 记录：enumerate_cliques。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((n + C) ceil(n / 64)) after O(n + m) graph
/// construction, where C is the number of cliques.
/// Space: O(n^2 / 64) g bits and O(n^2 / 64) recursion workspace.
#include <algorithm>
#include <bit>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Vertices are ordered by degree and every clique is generated exactly once
/// from its smallest vertex in that order. Recursion intersects the remaining
/// candidates with the chosen vertex's adjacency bitset, so only prefixes that
/// are already cliques are visited.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
int nw = (n + 63) / 64;
std::vector<int> deg(n);
for (auto [a, b] : es) {
deg[a]++;
deg[b]++;
}
std::vector<int> ord(n);
for (int i = 0; i < n; i++) {
ord[i] = i;
}
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
std::vector<std::vector<std::uint64_t>> g(n, std::vector<std::uint64_t>(nw));
for (auto [a, b] : es) {
a = rk[a];
b = rk[b];
g[a][b >> 6] |= std::uint64_t(1) << (b & 63);
g[b][a >> 6] |= std::uint64_t(1) << (a & 63);
}
T ans{};
auto dfs = [&](auto &self, std::vector<std::uint64_t> can,
const T &prd) -> void {
for (int wd = 0; wd < nw; wd++) {
while (can[wd] != 0) {
int bit = std::countr_zero(can[wd]);
int u = wd * 64 + bit;
can[wd] &= can[wd] - 1;
T np = prd * wt[ord[u]];
ans += np;
std::vector<std::uint64_t> nxt(nw);
for (int i = wd; i < nw; i++) {
nxt[i] = can[i] & g[u][i];
}
self(self, std::move(nxt), np);
}
}
};
std::vector<std::uint64_t> msk(nw, ~std::uint64_t(0));
if (n % 64 != 0) {
msk.back() = (std::uint64_t(1) << (n % 64)) - 1;
}
dfs(dfs, std::move(msk), T(1));
return ans;
}
} // namespace noya
#ifndef NOYA_CLIQUE_ENUMERATION_HPP
#define NOYA_CLIQUE_ENUMERATION_HPP 1
/// @complexity Time: O((n + C) ceil(n / 64)) after O(n + m) graph
/// construction, where C is the number of cliques.
/// Space: O(n^2 / 64) g bits and O(n^2 / 64) recursion workspace.
#include <algorithm>
#include <bit>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Vertices are ordered by degree and every clique is generated exactly once
/// from its smallest vertex in that order. Recursion intersects the remaining
/// candidates with the chosen vertex's adjacency bitset, so only prefixes that
/// are already cliques are visited.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
int nw = (n + 63) / 64;
std::vector<int> deg(n);
for (auto [a, b] : es) {
deg[a]++;
deg[b]++;
}
std::vector<int> ord(n);
for (int i = 0; i < n; i++) {
ord[i] = i;
}
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
std::vector<std::vector<std::uint64_t>> g(n, std::vector<std::uint64_t>(nw));
for (auto [a, b] : es) {
a = rk[a];
b = rk[b];
g[a][b >> 6] |= std::uint64_t(1) << (b & 63);
g[b][a >> 6] |= std::uint64_t(1) << (a & 63);
}
T ans{};
auto dfs = [&](auto &self, std::vector<std::uint64_t> can,
const T &prd) -> void {
for (int wd = 0; wd < nw; wd++) {
while (can[wd] != 0) {
int bit = std::countr_zero(can[wd]);
int u = wd * 64 + bit;
can[wd] &= can[wd] - 1;
T np = prd * wt[ord[u]];
ans += np;
std::vector<std::uint64_t> nxt(nw);
for (int i = wd; i < nw; i++) {
nxt[i] = can[i] & g[u][i];
}
self(self, std::move(nxt), np);
}
}
};
std::vector<std::uint64_t> msk(nw, ~std::uint64_t(0));
if (n % 64 != 0) {
msk.back() = (std::uint64_t(1) << (n % 64)) - 1;
}
dfs(dfs, std::move(msk), T(1));
return ans;
}
} // namespace noya
#endif // NOYA_CLIQUE_ENUMERATION_HPP
#include <algorithm>
#include <bit>
#include <cstdint>
#include <utility>
#include <vector>
/// @complexity Time: O((n + C) ceil(n / 64)) after O(n + m) graph
/// construction, where C is the number of cliques.
/// Space: O(n^2 / 64) g bits and O(n^2 / 64) recursion workspace.
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Vertices are ordered by degree and every clique is generated exactly once
/// from its smallest vertex in that order. Recursion intersects the remaining
/// candidates with the chosen vertex's adjacency bitset, so only prefixes that
/// are already cliques are visited.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
int nw = (n + 63) / 64;
std::vector<int> deg(n);
for (auto [a, b] : es) {
deg[a]++;
deg[b]++;
}
std::vector<int> ord(n);
for (int i = 0; i < n; i++) {
ord[i] = i;
}
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
std::vector<std::vector<std::uint64_t>> g(n, std::vector<std::uint64_t>(nw));
for (auto [a, b] : es) {
a = rk[a];
b = rk[b];
g[a][b >> 6] |= std::uint64_t(1) << (b & 63);
g[b][a >> 6] |= std::uint64_t(1) << (a & 63);
}
T ans{};
auto dfs = [&](auto &self, std::vector<std::uint64_t> can,
const T &prd) -> void {
for (int wd = 0; wd < nw; wd++) {
while (can[wd] != 0) {
int bit = std::countr_zero(can[wd]);
int u = wd * 64 + bit;
can[wd] &= can[wd] - 1;
T np = prd * wt[ord[u]];
ans += np;
std::vector<std::uint64_t> nxt(nw);
for (int i = wd; i < nw; i++) {
nxt[i] = can[i] & g[u][i];
}
self(self, std::move(nxt), np);
}
}
};
std::vector<std::uint64_t> msk(nw, ~std::uint64_t(0));
if (n % 64 != 0) {
msk.back() = (std::uint64_t(1) << (n % 64)) - 1;
}
dfs(dfs, std::move(msk), T(1));
return ans;
}
} // namespace noya