Tree Decomposition Width 2 (木幅2の木分解) (graph/others/tree-decomposition-width-2.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 10:02:02+00:00
• Include: #include "graph/others/tree-decomposition-width-2.hpp"
• Link: https://ei1333.hateblo.jp/entry/2020/02/12/150319

無向グラフが与えられたとき、木幅が $2$ 以下か判定し、$2$ 以下の場合は木幅 $2$ 以下の木分解を構成する。

非連結だとバグります！(適当にダミー辺を加えて連結にしてね)

コンストラクタ

explicit TreeDecompositionWidth2(int V)

頂点数 V のグラフで初期化します。

計算量

• $O(V)$

add_edge

void add_edge(int a, int b)

頂点 a、b 間に辺を張る。

build

vector<DecompNode> build()

木幅が $2$ 以下か判定し、$2$ 以下の場合はノード 0 を根とする木幅 $2$ 以下の木分解を返す。bag はそのノードに対応する頂点、child にはそのノードの子が格納される。$2$ より大きい場合は空列を返す。

計算量

• $O(E + V)$

to_nice

void to_nice(vector<DecompNode>& g, int root = 0)

木分解 g を Nice Tree-decomposition に変形する。これによりすべてのノードは、leaf(bag のサイズが $1$)、introduce($1$ つの子を持ち、子の bag に $1$ つの頂点を加えたもの)、forget($1$ つの子を持ち、子のbag から $1$ つの頂点を取り除いたもの)、join($2$ つの子を持ち、自身と $2$ つの子の bag はすべて同じ) のいずれかに属するようになる。

計算量

• $O(E + V)$

Verified with

• test/verify/aoj-2405.test.cpp
• test/verify/yosupo-tree-decomposition-width-2.test.cpp

Code

#pragma once

#include <algorithm>
#include <iterator>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>

/**
 * @brief Tree Decomposition Width 2(木幅2の木分解)
 * @see https://ei1333.hateblo.jp/entry/2020/02/12/150319
 *
 */
struct DecompNode {
  std::vector<int> bag, child;

  DecompNode() = default;
};

struct TreeDecompositionWidth2 {
  std::vector<std::vector<int> > g;

  explicit TreeDecompositionWidth2(int V) : g(V) {}

  void add_edge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  std::vector<DecompNode> build() {
    const int N = (int)g.size();

    std::vector<int> used(N, -1), deg(N);
    std::queue<int> que;
    for (int i = 0; i < N; i++) {
      deg[i] = (int)g[i].size();
      if (deg[i] <= 2) que.emplace(i);
    }

    std::vector<std::set<int> > exists(N);
    for (int i = 0; i < N; i++) {
      for (auto& j : g[i]) {
        if (i < j) exists[i].emplace(j);
      }
    }

    std::vector<DecompNode> ret;
    ret.emplace_back();
    while (!que.empty()) {
      int idx = que.front();
      que.pop();
      if (deg[idx] > 2 || used[idx] != -1) continue;

      DecompNode r;
      r.bag.emplace_back(idx);
      int u = -1, v = -1;
      for (auto& to : g[idx]) {
        if (used[to] == -1) {
          (u == -1 ? u : v) = to;
          r.bag.emplace_back(to);
        } else if (used[to] >= 0) {
          r.child.emplace_back(used[to]);
          used[to] = -2;
        }
      }

      if (u == -1) {
      } else if (v == -1) {
        --deg[u];
      } else {
        if (u > v) std::swap(u, v);
        if (!exists[u].count(v)) {
          g[u].emplace_back(v);
          g[v].emplace_back(u);
          exists[u].emplace(v);
        } else {
          --deg[u];
          --deg[v];
        }
      }

      for (auto& to : g[idx]) {
        if (deg[to] <= 2) que.emplace(to);
      }

      used[idx] = (int)ret.size();
      deg[idx] = 0;
      ret.emplace_back(r);
    }
    for (int i = 0; i < N; i++) {
      if (deg[i] > 0) return {};
    }
    ret.front() = ret.back();
    ret.pop_back();
    return ret;
  }
};

void to_nice(std::vector<DecompNode>& g, int root = 0) {
  for (auto& p : g) {
    std::sort(p.bag.begin(), p.bag.end());
  }

  std::stack<int> st;
  st.emplace(root);

  while (!st.empty()) {
    int idx = st.top();
    st.pop();

    // join
    while (g[idx].child.size() > 2) {
      DecompNode r;
      r.child.resize(2);
      r.child[0] = g[idx].child.back();
      g[idx].child.pop_back();
      r.child[1] = g[idx].child.back();
      g[idx].child.pop_back();
      r.bag = g[idx].bag;
      g[idx].child.emplace_back((int)g.size());
      g.emplace_back(r);
    }

    if (g[idx].child.size() == 2) {
      for (auto& ch : g[idx].child) {
        if (g[ch].bag != g[idx].bag) {
          DecompNode r;
          r.child = {ch};
          r.bag = g[idx].bag;
          ch = (int)g.size();
          g.emplace_back(r);
        }
      }
    }

    // introduce / forget
    if (g[idx].child.size() == 1) {
      int& ch = g[idx].child[0];

      std::vector<int> latte, malta;
      std::set_difference(g[idx].bag.begin(), g[idx].bag.end(),
                          g[ch].bag.begin(), g[ch].bag.end(),
                          std::back_inserter(latte));
      std::set_difference(g[ch].bag.begin(), g[ch].bag.end(),
                          g[idx].bag.begin(), g[idx].bag.end(),
                          std::back_inserter(malta));
      if (latte.size() + malta.size() > 1) {
        DecompNode r;
        r.child = {ch};
        r.bag = g[idx].bag;
        if (!latte.empty()) {
          r.bag.erase(std::find(r.bag.begin(), r.bag.end(), latte.back()));
        } else {
          r.bag.emplace_back(malta.back());
        }
        ch = (int)g.size();
        g.emplace_back(r);
      }
    }

    // leaf
    if (g[idx].child.empty()) {
      if (g[idx].bag.size() > 1) {
        DecompNode r;
        r.bag = g[idx].bag;
        r.bag.pop_back();
        g[idx].child.emplace_back((int)g.size());
        g.emplace_back(r);
      }
    }

    for (auto& ch : g[idx].child) {
      st.emplace(ch);
    }
  }
}

#line 2 "graph/others/tree-decomposition-width-2.hpp"

#include <algorithm>
#include <iterator>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>

/**
 * @brief Tree Decomposition Width 2(木幅2の木分解)
 * @see https://ei1333.hateblo.jp/entry/2020/02/12/150319
 *
 */
struct DecompNode {
  std::vector<int> bag, child;

  DecompNode() = default;
};

struct TreeDecompositionWidth2 {
  std::vector<std::vector<int> > g;

  explicit TreeDecompositionWidth2(int V) : g(V) {}

  void add_edge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  std::vector<DecompNode> build() {
    const int N = (int)g.size();

    std::vector<int> used(N, -1), deg(N);
    std::queue<int> que;
    for (int i = 0; i < N; i++) {
      deg[i] = (int)g[i].size();
      if (deg[i] <= 2) que.emplace(i);
    }

    std::vector<std::set<int> > exists(N);
    for (int i = 0; i < N; i++) {
      for (auto& j : g[i]) {
        if (i < j) exists[i].emplace(j);
      }
    }

    std::vector<DecompNode> ret;
    ret.emplace_back();
    while (!que.empty()) {
      int idx = que.front();
      que.pop();
      if (deg[idx] > 2 || used[idx] != -1) continue;

      DecompNode r;
      r.bag.emplace_back(idx);
      int u = -1, v = -1;
      for (auto& to : g[idx]) {
        if (used[to] == -1) {
          (u == -1 ? u : v) = to;
          r.bag.emplace_back(to);
        } else if (used[to] >= 0) {
          r.child.emplace_back(used[to]);
          used[to] = -2;
        }
      }

      if (u == -1) {
      } else if (v == -1) {
        --deg[u];
      } else {
        if (u > v) std::swap(u, v);
        if (!exists[u].count(v)) {
          g[u].emplace_back(v);
          g[v].emplace_back(u);
          exists[u].emplace(v);
        } else {
          --deg[u];
          --deg[v];
        }
      }

      for (auto& to : g[idx]) {
        if (deg[to] <= 2) que.emplace(to);
      }

      used[idx] = (int)ret.size();
      deg[idx] = 0;
      ret.emplace_back(r);
    }
    for (int i = 0; i < N; i++) {
      if (deg[i] > 0) return {};
    }
    ret.front() = ret.back();
    ret.pop_back();
    return ret;
  }
};

void to_nice(std::vector<DecompNode>& g, int root = 0) {
  for (auto& p : g) {
    std::sort(p.bag.begin(), p.bag.end());
  }

  std::stack<int> st;
  st.emplace(root);

  while (!st.empty()) {
    int idx = st.top();
    st.pop();

    // join
    while (g[idx].child.size() > 2) {
      DecompNode r;
      r.child.resize(2);
      r.child[0] = g[idx].child.back();
      g[idx].child.pop_back();
      r.child[1] = g[idx].child.back();
      g[idx].child.pop_back();
      r.bag = g[idx].bag;
      g[idx].child.emplace_back((int)g.size());
      g.emplace_back(r);
    }

    if (g[idx].child.size() == 2) {
      for (auto& ch : g[idx].child) {
        if (g[ch].bag != g[idx].bag) {
          DecompNode r;
          r.child = {ch};
          r.bag = g[idx].bag;
          ch = (int)g.size();
          g.emplace_back(r);
        }
      }
    }

    // introduce / forget
    if (g[idx].child.size() == 1) {
      int& ch = g[idx].child[0];

      std::vector<int> latte, malta;
      std::set_difference(g[idx].bag.begin(), g[idx].bag.end(),
                          g[ch].bag.begin(), g[ch].bag.end(),
                          std::back_inserter(latte));
      std::set_difference(g[ch].bag.begin(), g[ch].bag.end(),
                          g[idx].bag.begin(), g[idx].bag.end(),
                          std::back_inserter(malta));
      if (latte.size() + malta.size() > 1) {
        DecompNode r;
        r.child = {ch};
        r.bag = g[idx].bag;
        if (!latte.empty()) {
          r.bag.erase(std::find(r.bag.begin(), r.bag.end(), latte.back()));
        } else {
          r.bag.emplace_back(malta.back());
        }
        ch = (int)g.size();
        g.emplace_back(r);
      }
    }

    // leaf
    if (g[idx].child.empty()) {
      if (g[idx].bag.size() > 1) {
        DecompNode r;
        r.bag = g[idx].bag;
        r.bag.pop_back();
        g[idx].child.emplace_back((int)g.size());
        g.emplace_back(r);
      }
    }

    for (auto& ch : g[idx].child) {
      st.emplace(ch);
    }
  }
}

Back to top page