tree_decomposition_width_two.hpp¶
识别简单无向图的树宽是否至多为 2，并用固定邻居槽、复用边哈希表恢复树分解；返回的 w 是该分解宽度，不保证为最小树宽。
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 <array>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#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
/// neighbors, 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.
/// Input is a simple undirected graph: valid endpoints, no loops or duplicate
/// unordered edges. Disconnected/empty graphs are allowed; input is unchanged.
/// Return nullopt exactly when treewidth exceeds two. Success has n bags in
/// reverse elimination order, joined into one tree (n-1 edges when n>0).
/// w is the largest bag size minus one (0 for empty), not the minimum treewidth.
/// Bag/member/edge ordering matches the original LIFO reduction. Expected time
/// assumes ordinary hash-table behavior; adversarial collisions may be slower.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
// A simple graph of treewidth at most two has at most 2n-3 edges.
if (n >= 2 && es1.size() > 2 * std::size_t(n) - 3) return std::nullopt;
std::vector<int> deg(n);
for (auto [a, b] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a];
++deg[b];
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u) if (deg[u] <= 2) q.push_back(u);
if (n && q.empty()) return std::nullopt;
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
std::unordered_map<std::uint64_t, int> eb;
// At most one fill edge per removed vertex. Reuse this table later to
// record the latest bag containing each edge; no second hash table is needed.
eb.reserve(es1.size() + std::size_t(n));
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) {
bool ins = eb.emplace(key(a, b), -1).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<bool> ok(n, true);
std::vector<std::array<int, 2>> 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;
}
auto &adj = ln[u];
int count = 0;
for (int nxt : g[u]) {
if (ok[nxt]) {
assert(count < 2);
adj[count++] = nxt;
}
}
assert(count == deg[u]);
ord.push_back(u);
ok[u] = false;
for (int i = 0; i < count; ++i) {
int nxt = adj[i];
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (count == 2) {
int a = adj[0];
int b = adj[1];
if (eb.emplace(key(a, b), -1).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);
res.es.reserve(n ? n - 1 : 0);
std::vector<int> bcv(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.reserve(deg[u] + 1);
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].begin() + deg[u]);
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (deg[u] == 1) {
fa = bcv[ln[u][0]];
} else if (deg[u] == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
assert(fa >= 0);
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (deg[u] == 0) {
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
// NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP
#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 <array>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#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
/// neighbors, 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.
/// Input is a simple undirected graph: valid endpoints, no loops or duplicate
/// unordered edges. Disconnected/empty graphs are allowed; input is unchanged.
/// Return nullopt exactly when treewidth exceeds two. Success has n bags in
/// reverse elimination order, joined into one tree (n-1 edges when n>0).
/// w is the largest bag size minus one (0 for empty), not the minimum treewidth.
/// Bag/member/edge ordering matches the original LIFO reduction. Expected time
/// assumes ordinary hash-table behavior; adversarial collisions may be slower.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
// A simple graph of treewidth at most two has at most 2n-3 edges.
if (n >= 2 && es1.size() > 2 * std::size_t(n) - 3) return std::nullopt;
std::vector<int> deg(n);
for (auto [a, b] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a];
++deg[b];
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u) if (deg[u] <= 2) q.push_back(u);
if (n && q.empty()) return std::nullopt;
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
std::unordered_map<std::uint64_t, int> eb;
// At most one fill edge per removed vertex. Reuse this table later to
// record the latest bag containing each edge; no second hash table is needed.
eb.reserve(es1.size() + std::size_t(n));
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) {
bool ins = eb.emplace(key(a, b), -1).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<bool> ok(n, true);
std::vector<std::array<int, 2>> 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;
}
auto &adj = ln[u];
int count = 0;
for (int nxt : g[u]) {
if (ok[nxt]) {
assert(count < 2);
adj[count++] = nxt;
}
}
assert(count == deg[u]);
ord.push_back(u);
ok[u] = false;
for (int i = 0; i < count; ++i) {
int nxt = adj[i];
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (count == 2) {
int a = adj[0];
int b = adj[1];
if (eb.emplace(key(a, b), -1).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);
res.es.reserve(n ? n - 1 : 0);
std::vector<int> bcv(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.reserve(deg[u] + 1);
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].begin() + deg[u]);
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (deg[u] == 1) {
fa = bcv[ln[u][0]];
} else if (deg[u] == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
assert(fa >= 0);
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (deg[u] == 0) {
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
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#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
/// neighbors, 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.
/// Input is a simple undirected graph: valid endpoints, no loops or duplicate
/// unordered edges. Disconnected/empty graphs are allowed; input is unchanged.
/// Return nullopt exactly when treewidth exceeds two. Success has n bags in
/// reverse elimination order, joined into one tree (n-1 edges when n>0).
/// w is the largest bag size minus one (0 for empty), not the minimum treewidth.
/// Bag/member/edge ordering matches the original LIFO reduction. Expected time
/// assumes ordinary hash-table behavior; adversarial collisions may be slower.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(int n,
const std::vector<std::pair<int, int>> &es1) {
assert(n >= 0);
// A simple graph of treewidth at most two has at most 2n-3 edges.
if (n >= 2 && es1.size() > 2 * std::size_t(n) - 3) return std::nullopt;
std::vector<int> deg(n);
for (auto [a, b] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a];
++deg[b];
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u) if (deg[u] <= 2) q.push_back(u);
if (n && q.empty()) return std::nullopt;
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
std::unordered_map<std::uint64_t, int> eb;
// At most one fill edge per removed vertex. Reuse this table later to
// record the latest bag containing each edge; no second hash table is needed.
eb.reserve(es1.size() + std::size_t(n));
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) {
bool ins = eb.emplace(key(a, b), -1).second;
assert(ins);
if (!ins) {
continue;
}
g[a].push_back(b);
g[b].push_back(a);
}
std::vector<bool> ok(n, true);
std::vector<std::array<int, 2>> 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;
}
auto &adj = ln[u];
int count = 0;
for (int nxt : g[u]) {
if (ok[nxt]) {
assert(count < 2);
adj[count++] = nxt;
}
}
assert(count == deg[u]);
ord.push_back(u);
ok[u] = false;
for (int i = 0; i < count; ++i) {
int nxt = adj[i];
deg[nxt]--;
if (deg[nxt] <= 2) {
q.push_back(nxt);
}
}
if (count == 2) {
int a = adj[0];
int b = adj[1];
if (eb.emplace(key(a, b), -1).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);
res.es.reserve(n ? n - 1 : 0);
std::vector<int> bcv(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.reserve(deg[u] + 1);
bag.push_back(u);
bag.insert(bag.end(), ln[u].begin(), ln[u].begin() + deg[u]);
res.w = std::max(res.w, int(bag.size()) - 1);
int fa = -1;
if (deg[u] == 1) {
fa = bcv[ln[u][0]];
} else if (deg[u] == 2) {
fa = eb.at(key(ln[u][0], ln[u][1]));
assert(fa >= 0);
} else if (pr != -1) {
fa = pr;
}
if (fa != -1) {
res.es.emplace_back(fa, id);
}
if (deg[u] == 0) {
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
// NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP