Euler tour technique
(include/emthrm/graph/tree/euler_tour_technique.hpp)

View this file on GitHub
Last update: 2023-05-12 15:57:02+09:00
Include: #include "emthrm/graph/tree/euler_tour_technique.hpp"

根付き木を列として表現するデータ構造である。

時間計算量

$O(\lvert V \rvert)$

仕様

template <typename CostType>
struct EulerTourTechnique;

CostType：辺のコストを表す型

メンバ変数

名前	説明
`std::vector<int> preorder`	頂点属性の Euler tour
`std::vector<int> depth`	`depth[i]` は頂点 `preorder[i]` の深さを表す。
`std::vector<int> left`	`left[i]` は `preorder` に頂点 $i$ が現れるインデックスの最小値を表す。
`std::vector<int> right`	`right[i]` は `preorder` に頂点 $i$ が現れるインデックスの最大値を表す。
`std::vector<int> down`	`down[i]` は `tour` に頂点 $i$ へ下る辺が現れるインデックスを表す。
`std::vector<int> up`	`up[i]` は `tour` に頂点 $i$ から上る辺が現れるインデックスを表す。
`std::vector<CostType> tour`	Euler tour

メンバ関数

名前	効果・戻り値
`explicit EulerTourTechnique(const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0);`	根を $\mathrm{root}$ とする木 $\mathrm{graph}$ に対してオブジェクトを構築する。
`template <typename Fn>` `void update_v(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の頂点に対して $f$ を基に更新する。
`template <typename T, typename Fn>` `T query_v(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の頂点に対する $f$ を基にしたクエリの解
`template <typename T, typename Fn>` `T query_e(const int u, const int v, const Fn f) const;`	頂点 $u$ から $v$ へ下る辺に対する $f$ を基にしたクエリの解
`template <typename Fn>` `void update_subtree_e(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の辺に対して $f$ を基に更新する。
`template <typename T, typename Fn>` `T query_subtree_e(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の辺に対する $f$ を基にしたクエリの解

参考文献

Robert E. Tarjan and Uzi Vishkin: Finding biconnected componemts and computing tree functions in logarithmic parallel time, 25th Annual Symposium on Foundations of Computer Science, 1984., pp. 12–20 (1984). https://doi.org/10.1109/SFCS.1984.715896
~~http://beet-aizu.hatenablog.com/entry/2019/07/08/174727~~
https://twitter.com/3SAT_IS_IN_P/status/1296040678820990982
https://github.com/spaghetti-source/algorithm/blob/41bc0bbb1767692eb9bdeeceb332b2b8cc17329a/graph/least_common_ancestor_sparsetable.cc

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2667/review/4084875/emthrm/C++14

Depends on

辺 (include/emthrm/graph/edge.hpp)

Required by

最小共通祖先 (lowest common ancestor) Euler tour technique 版 (include/emthrm/graph/tree/lowest_common_ancestor_by_euler_tour_technique.hpp)

Verified with

グラフ/木/最小共通祖先 Euler tour technique 版 (test/graph/tree/lowest_common_ancestor_by_euler_tour.test.cpp)

Code

#ifndef EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_
#define EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_

#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
struct EulerTourTechnique {
  std::vector<int> preorder, depth, left, right, down, up;
  std::vector<CostType> tour;

  explicit EulerTourTechnique(
      const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0)
      : graph(graph) {
    const int n = graph.size();
    left.resize(n);
    right.resize(n);
    down.assign(n, -1);
    up.assign(n, (n - 1) << 1);
    dfs(-1, root, 0);
  }

  template <typename Fn>
  void update_v(const int ver, const Fn f) const {
    f(left[ver], right[ver] + 1);
  }

  template <typename T, typename Fn>
  T query_v(const int ver, const Fn f) const {
    return f(left[ver], right[ver] + 1);
  }

  template <typename T, typename Fn>
  T query_e(const int u, const int v, const Fn f) const {
    return f(down[u] + 1, down[v] + 1);
  }

  template <typename Fn>
  void update_subtree_e(const int ver, const Fn f) const {
    f(down[ver] + 1, up[ver]);
  }

  template <typename T, typename Fn>
  T query_subtree_e(const int ver, const Fn f) const {
    return f(down[ver] + 1, up[ver]);
  }

 private:
  const std::vector<std::vector<Edge<CostType>>> graph;

  void dfs(const int par, const int ver, const int cur_depth) {
    left[ver] = preorder.size();
    preorder.emplace_back(ver);
    depth.emplace_back(cur_depth);
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) {
        down[e.dst] = tour.size();
        tour.emplace_back(e.cost);
        dfs(ver, e.dst, cur_depth + 1);
        preorder.emplace_back(ver);
        depth.emplace_back(cur_depth);
        up[e.dst] = tour.size();
        tour.emplace_back(-e.cost);
      }
    }
    right[ver] = preorder.size() - 1;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_

#line 1 "include/emthrm/graph/tree/euler_tour_technique.hpp"



#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 7 "include/emthrm/graph/tree/euler_tour_technique.hpp"

namespace emthrm {

template <typename CostType>
struct EulerTourTechnique {
  std::vector<int> preorder, depth, left, right, down, up;
  std::vector<CostType> tour;

  explicit EulerTourTechnique(
      const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0)
      : graph(graph) {
    const int n = graph.size();
    left.resize(n);
    right.resize(n);
    down.assign(n, -1);
    up.assign(n, (n - 1) << 1);
    dfs(-1, root, 0);
  }

  template <typename Fn>
  void update_v(const int ver, const Fn f) const {
    f(left[ver], right[ver] + 1);
  }

  template <typename T, typename Fn>
  T query_v(const int ver, const Fn f) const {
    return f(left[ver], right[ver] + 1);
  }

  template <typename T, typename Fn>
  T query_e(const int u, const int v, const Fn f) const {
    return f(down[u] + 1, down[v] + 1);
  }

  template <typename Fn>
  void update_subtree_e(const int ver, const Fn f) const {
    f(down[ver] + 1, up[ver]);
  }

  template <typename T, typename Fn>
  T query_subtree_e(const int ver, const Fn f) const {
    return f(down[ver] + 1, up[ver]);
  }

 private:
  const std::vector<std::vector<Edge<CostType>>> graph;

  void dfs(const int par, const int ver, const int cur_depth) {
    left[ver] = preorder.size();
    preorder.emplace_back(ver);
    depth.emplace_back(cur_depth);
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) {
        down[e.dst] = tour.size();
        tour.emplace_back(e.cost);
        dfs(ver, e.dst, cur_depth + 1);
        preorder.emplace_back(ver);
        depth.emplace_back(cur_depth);
        up[e.dst] = tour.size();
        tour.emplace_back(-e.cost);
      }
    }
    right[ver] = preorder.size() - 1;
  }
};

}  // namespace emthrm

Euler tour technique (include/emthrm/graph/tree/euler_tour_technique.hpp)

時間計算量

仕様

メンバ変数

メンバ関数

参考文献

Submissons

Depends on

Required by

Verified with

Code

Euler tour technique
(include/emthrm/graph/tree/euler_tour_technique.hpp)