test/yosupo/tree_decomposition_width_2.test.cpp

View this file on GitHub
Last update: 2024-01-08 13:32:33+09:00
Problem: https://judge.yosupo.jp/problem/tree_decomposition_width_2

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/tree_decomposition_width_2"

#include <bits/stdc++.h>

#include "../../graph/junction_tree.hpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string _s;
    cin >> _s >> _s;
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    JunctionTreeWidth2 jt(G);
    if (!jt.is_treewidth_2()) {
        cout << -1 << "\n";
        return 0;
    }
    auto nodes = jt.get_nodes();
    int K = jt.size();
    cout << "s td " << K << " 2 " << N << "\n";
    for (int i = 0; i < K; ++i) {
        cout << "b " << i + 1;
        for (int v : nodes[i].bag) {
            cout << " " << v + 1;
        }
        cout << "\n";
    }
    for (int i = 0; i < K; ++i) {
        for (int c : nodes[i].ch) {
            cout << i + 1 << " " << c + 1 << "\n";
        }
    }
}

#line 1 "test/yosupo/tree_decomposition_width_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/tree_decomposition_width_2"

#include <bits/stdc++.h>

#line 5 "graph/junction_tree.hpp"

#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;
};
#line 6 "test/yosupo/tree_decomposition_width_2.test.cpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string _s;
    cin >> _s >> _s;
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    JunctionTreeWidth2 jt(G);
    if (!jt.is_treewidth_2()) {
        cout << -1 << "\n";
        return 0;
    }
    auto nodes = jt.get_nodes();
    int K = jt.size();
    cout << "s td " << K << " 2 " << N << "\n";
    for (int i = 0; i < K; ++i) {
        cout << "b " << i + 1;
        for (int v : nodes[i].bag) {
            cout << " " << v + 1;
        }
        cout << "\n";
    }
    for (int i = 0; i < K; ++i) {
        for (int c : nodes[i].ch) {
            cout << i + 1 << " " << c + 1 << "\n";
        }
    }
}