sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/junction_tree.hpp"
与えられた木の木幅が $2$ 以下か判定し,そうならば木幅 $2$ の木分解を構築する.
空間計算量: $O(V + E)$
JunctionTreeWidth2(vector<vector<int>> G)
bool is_treewidth_2()
vector<Node> get_nodes()
Node
bag
ch
#pragma once #include <set> #include <stack> #include <vector> #include "../data-structure/unionfind/union_find.hpp" class JunctionTreeWidth2 { public: struct Node { std::vector<int> bag; std::vector<int> ch; }; explicit JunctionTreeWidth2(const std::vector<std::vector<int>>& G) : nodes(1) { const int n = G.size(); UnionFind uf(n); std::vector<int> deg(n); std::vector<std::set<int>> G_st(n); for (int v = 0; v < n; ++v) { for (int u : G[v]) { uf.unite(u, v); G_st[v].insert(u); } deg[v] = G_st[v].size(); } // add dummy edges to make G connected std::vector<int> leaders; for (int v = 0; v < n; ++v) { if (uf.find(v) == v) { leaders.push_back(v); } } for (int i = 0; i < (int)leaders.size() - 1; ++i) { int u = leaders[i]; int v = leaders[i + 1]; G_st[u].insert(v); G_st[v].insert(u); ++deg[u], ++deg[v]; } // construct a tree decomposition of width 2 // -2: removed and added to the tree // -1: not removed // >= 0: removed and not yet added to the tree std::vector<int> state(n, -1); std::stack<int> st; for (int v = 0; v < n; ++v) { if (deg[v] <= 2) { st.push(v); } } while (!st.empty()) { int v = st.top(); st.pop(); if (state[v] != -1) continue; Node node; node.bag.push_back(v); int x = -1, y = -1; for (int u : G_st[v]) { if (state[u] == -1) { (x == -1 ? x : y) = u; node.bag.push_back(u); } else if (state[u] > 0) { node.ch.push_back(state[u]); state[u] = -2; } } if (x == -1) { // last vertex } else if (y == -1) { --deg[x]; } else { // add new edge if (!G_st[x].contains(y)) { G_st[x].insert(y); G_st[y].insert(x); } else { --deg[x], --deg[y]; } } for (int u : G_st[v]) { if (state[u] == -1 && deg[u] <= 2) { st.push(u); } } deg[v] = 0; state[v] = nodes.size(); nodes.push_back(node); } if (*std::ranges::max_element(deg) > 0) { treewidth_is_2 = false; return; } treewidth_is_2 = true; nodes[0].ch.push_back(nodes.size() - 1); } bool is_treewidth_2() const { return treewidth_is_2; } int size() const { return nodes.size(); } std::vector<Node> get_nodes() const { return nodes; } private: bool treewidth_is_2; std::vector<Node> nodes; };
#line 2 "graph/junction_tree.hpp" #include <set> #include <stack> #include <vector> #line 2 "data-structure/unionfind/union_find.hpp" #include <algorithm> #line 4 "data-structure/unionfind/union_find.hpp" class UnionFind { public: UnionFind() = default; explicit UnionFind(int n) : data(n, -1) {} int find(int x) { if (data[x] < 0) return x; return data[x] = find(data[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (data[x] > data[y]) std::swap(x, y); data[x] += data[y]; data[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -data[find(x)]; } private: std::vector<int> data; }; #line 7 "graph/junction_tree.hpp" class JunctionTreeWidth2 { public: struct Node { std::vector<int> bag; std::vector<int> ch; }; explicit JunctionTreeWidth2(const std::vector<std::vector<int>>& G) : nodes(1) { const int n = G.size(); UnionFind uf(n); std::vector<int> deg(n); std::vector<std::set<int>> G_st(n); for (int v = 0; v < n; ++v) { for (int u : G[v]) { uf.unite(u, v); G_st[v].insert(u); } deg[v] = G_st[v].size(); } // add dummy edges to make G connected std::vector<int> leaders; for (int v = 0; v < n; ++v) { if (uf.find(v) == v) { leaders.push_back(v); } } for (int i = 0; i < (int)leaders.size() - 1; ++i) { int u = leaders[i]; int v = leaders[i + 1]; G_st[u].insert(v); G_st[v].insert(u); ++deg[u], ++deg[v]; } // construct a tree decomposition of width 2 // -2: removed and added to the tree // -1: not removed // >= 0: removed and not yet added to the tree std::vector<int> state(n, -1); std::stack<int> st; for (int v = 0; v < n; ++v) { if (deg[v] <= 2) { st.push(v); } } while (!st.empty()) { int v = st.top(); st.pop(); if (state[v] != -1) continue; Node node; node.bag.push_back(v); int x = -1, y = -1; for (int u : G_st[v]) { if (state[u] == -1) { (x == -1 ? x : y) = u; node.bag.push_back(u); } else if (state[u] > 0) { node.ch.push_back(state[u]); state[u] = -2; } } if (x == -1) { // last vertex } else if (y == -1) { --deg[x]; } else { // add new edge if (!G_st[x].contains(y)) { G_st[x].insert(y); G_st[y].insert(x); } else { --deg[x], --deg[y]; } } for (int u : G_st[v]) { if (state[u] == -1 && deg[u] <= 2) { st.push(u); } } deg[v] = 0; state[v] = nodes.size(); nodes.push_back(node); } if (*std::ranges::max_element(deg) > 0) { treewidth_is_2 = false; return; } treewidth_is_2 = true; nodes[0].ch.push_back(nodes.size() - 1); } bool is_treewidth_2() const { return treewidth_is_2; } int size() const { return nodes.size(); } std::vector<Node> get_nodes() const { return nodes; } private: bool treewidth_is_2; std::vector<Node> nodes; };