tree_decomposition_width_two.hpp¶
识别并构造宽度不超过 2 的树分解；适合系列并行图或小树宽 DP。
Complexity: Time: Expected O(V + E). Space: O(V + E).
AC 记录：tree_decomposition_width_2。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace noya {
struct width_two_tree_decomposition {
int w = 0;
std::vector<std::vector<int>> ba1;
std::vector<std::pair<int, int>> es;
};
/// @brief Recognize treewidth at most two and construct a decomposition.
/// Repeatedly remove a live vertex of degree at most two; when it has two
/// adj, add the missing edge between them. This reduction is exact:
/// suppressing a degree-two vertex produces a minor, while a decomposition of
/// the filled graph extends by attaching the bag {vertex, first, second}.
/// Reversing the eliminations and attaching each new bag to a later bag that
/// contains its surviving neighbor set yields bags of size at most three.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::unordered_set<std::uint64_t> vis;
vis.reserve(2 * (es1.size() + std::size_t(n)) + 1);
auto key = [](int a, int b) {
if (a > b) {
std::swap(a, b);
}
return (std::uint64_t(std::uint32_t(a)) << 32) | std::uint32_t(b);
};
for (auto [a, b] : es1) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
bool ins = vis.insert(key(a, b)).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<int> deg(n);
std::vector<bool> ok(n, true);
std::vector<int> q;
q.reserve(n + 2 * es1.size());
for (int u = 0; u < n; u++) {
deg[u] = int(g[u].size());
if (deg[u] <= 2) {
q.push_back(u);
}
}
std::vector<std::vector<int>> ln(n);
std::vector<int> ord;
ord.reserve(n);
while (!q.empty()) {
int u = q.back();
q.pop_back();
if (!ok[u] || deg[u] > 2) {
continue;
}
std::vector<int> adj;
for (int nxt : g[u]) {
if (ok[nxt]) {
adj.push_back(nxt);
}
}
assert(int(adj.size()) == deg[u]);
ln[u] = adj;
ord.push_back(u);
ok[u] = false;
for (int nxt : adj) {
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (adj.size() == 2) {
int a = adj[0];
int b = adj[1];
if (vis.insert(key(a, b)).second) {
g[a].push_back(b);
g[b].push_back(a);
deg[a]++;
deg[b]++;
}
}
}
if (int(ord.size()) != n) {
return std::nullopt;
}
width_two_tree_decomposition res;
res.ba1.resize(n);
std::vector<int> bcv(n, -1);
std::unordered_map<std::uint64_t, int> eb;
eb.reserve(2 * (es1.size() + std::size_t(n)) + 1);
int crt = 0;
int pr = -1;
for (auto it = ord.rbegin(); it != ord.rend(); ++it) {
int u = *it;
int id = crt++;
std::vector<int> &bag = res.ba1[id];
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].end());
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (ln[u].size() == 1) {
fa = bcv[ln[u][0]];
} else if (ln[u].size() == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (ln[u].empty()) {
pr = id;
}
for (int mem : bag) {
bcv[mem] = id;
}
for (int a = 0; a < int(bag.size()); a++) {
for (int b = a + 1; b < int(bag.size()); b++) {
eb[key(bag[a], bag[b])] = id;
}
}
}
return res;
}
} // namespace noya
#ifndef NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP
#define NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP 1
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace noya {
struct width_two_tree_decomposition {
int w = 0;
std::vector<std::vector<int>> ba1;
std::vector<std::pair<int, int>> es;
};
/// @brief Recognize treewidth at most two and construct a decomposition.
/// Repeatedly remove a live vertex of degree at most two; when it has two
/// adj, add the missing edge between them. This reduction is exact:
/// suppressing a degree-two vertex produces a minor, while a decomposition of
/// the filled graph extends by attaching the bag {vertex, first, second}.
/// Reversing the eliminations and attaching each new bag to a later bag that
/// contains its surviving neighbor set yields bags of size at most three.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::unordered_set<std::uint64_t> vis;
vis.reserve(2 * (es1.size() + std::size_t(n)) + 1);
auto key = [](int a, int b) {
if (a > b) {
std::swap(a, b);
}
return (std::uint64_t(std::uint32_t(a)) << 32) | std::uint32_t(b);
};
for (auto [a, b] : es1) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
bool ins = vis.insert(key(a, b)).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<int> deg(n);
std::vector<bool> ok(n, true);
std::vector<int> q;
q.reserve(n + 2 * es1.size());
for (int u = 0; u < n; u++) {
deg[u] = int(g[u].size());
if (deg[u] <= 2) {
q.push_back(u);
}
}
std::vector<std::vector<int>> ln(n);
std::vector<int> ord;
ord.reserve(n);
while (!q.empty()) {
int u = q.back();
q.pop_back();
if (!ok[u] || deg[u] > 2) {
continue;
}
std::vector<int> adj;
for (int nxt : g[u]) {
if (ok[nxt]) {
adj.push_back(nxt);
}
}
assert(int(adj.size()) == deg[u]);
ln[u] = adj;
ord.push_back(u);
ok[u] = false;
for (int nxt : adj) {
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (adj.size() == 2) {
int a = adj[0];
int b = adj[1];
if (vis.insert(key(a, b)).second) {
g[a].push_back(b);
g[b].push_back(a);
deg[a]++;
deg[b]++;
}
}
}
if (int(ord.size()) != n) {
return std::nullopt;
}
width_two_tree_decomposition res;
res.ba1.resize(n);
std::vector<int> bcv(n, -1);
std::unordered_map<std::uint64_t, int> eb;
eb.reserve(2 * (es1.size() + std::size_t(n)) + 1);
int crt = 0;
int pr = -1;
for (auto it = ord.rbegin(); it != ord.rend(); ++it) {
int u = *it;
int id = crt++;
std::vector<int> &bag = res.ba1[id];
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].end());
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (ln[u].size() == 1) {
fa = bcv[ln[u][0]];
} else if (ln[u].size() == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (ln[u].empty()) {
pr = id;
}
for (int mem : bag) {
bcv[mem] = id;
}
for (int a = 0; a < int(bag.size()); a++) {
for (int b = a + 1; b < int(bag.size()); b++) {
eb[key(bag[a], bag[b])] = id;
}
}
}
return res;
}
} // namespace noya
#endif // NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
namespace noya {
struct width_two_tree_decomposition {
int w = 0;
std::vector<std::vector<int>> ba1;
std::vector<std::pair<int, int>> es;
};
/// @brief Recognize treewidth at most two and construct a decomposition.
/// Repeatedly remove a live vertex of degree at most two; when it has two
/// adj, add the missing edge between them. This reduction is exact:
/// suppressing a degree-two vertex produces a minor, while a decomposition of
/// the filled graph extends by attaching the bag {vertex, first, second}.
/// Reversing the eliminations and attaching each new bag to a later bag that
/// contains its surviving neighbor set yields bags of size at most three.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::unordered_set<std::uint64_t> vis;
vis.reserve(2 * (es1.size() + std::size_t(n)) + 1);
auto key = [](int a, int b) {
if (a > b) {
std::swap(a, b);
}
return (std::uint64_t(std::uint32_t(a)) << 32) | std::uint32_t(b);
};
for (auto [a, b] : es1) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
bool ins = vis.insert(key(a, b)).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<int> deg(n);
std::vector<bool> ok(n, true);
std::vector<int> q;
q.reserve(n + 2 * es1.size());
for (int u = 0; u < n; u++) {
deg[u] = int(g[u].size());
if (deg[u] <= 2) {
q.push_back(u);
}
}
std::vector<std::vector<int>> ln(n);
std::vector<int> ord;
ord.reserve(n);
while (!q.empty()) {
int u = q.back();
q.pop_back();
if (!ok[u] || deg[u] > 2) {
continue;
}
std::vector<int> adj;
for (int nxt : g[u]) {
if (ok[nxt]) {
adj.push_back(nxt);
}
}
assert(int(adj.size()) == deg[u]);
ln[u] = adj;
ord.push_back(u);
ok[u] = false;
for (int nxt : adj) {
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (adj.size() == 2) {
int a = adj[0];
int b = adj[1];
if (vis.insert(key(a, b)).second) {
g[a].push_back(b);
g[b].push_back(a);
deg[a]++;
deg[b]++;
}
}
}
if (int(ord.size()) != n) {
return std::nullopt;
}
width_two_tree_decomposition res;
res.ba1.resize(n);
std::vector<int> bcv(n, -1);
std::unordered_map<std::uint64_t, int> eb;
eb.reserve(2 * (es1.size() + std::size_t(n)) + 1);
int crt = 0;
int pr = -1;
for (auto it = ord.rbegin(); it != ord.rend(); ++it) {
int u = *it;
int id = crt++;
std::vector<int> &bag = res.ba1[id];
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].end());
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (ln[u].size() == 1) {
fa = bcv[ln[u][0]];
} else if (ln[u].size() == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (ln[u].empty()) {
pr = id;
}
for (int mem : bag) {
bcv[mem] = id;
}
for (int a = 0; a < int(bag.size()); a++) {
for (int b = a + 1; b < int(bag.size()); b++) {
eb[key(bag[a], bag[b])] = id;
}
}
}
return res;
}
} // namespace noya