Euler Tour of Tree
(tree/euler-tour.hpp)

• View this file on GitHub
• Last update: 2026-09-05 04:46:11+09:00
• Include: #include "tree/euler-tour.hpp"

根付き木を Euler Tour の行きがけ順に並べる．

非空の連結な木を受け取り，各辺は行き先 to を持つものとする．

• EulerTour(g, root)：木 g を根 root から走査し，{in_time, out_time} を返す．
• in_time[x]：頂点 $x$ を訪れる時刻．
• out_time[x]：頂点 $x$ の部分木を抜ける時刻．

頂点 $x$ の部分木は，行きがけ順の半開区間 $[in_time[x],out_time[x])$ に対応する．

時間計算量と空間計算量は $O(N)$．

Required by

• Tree Vertex Set Subtree Product (tree/tree-vertex-set-subtree-prod.hpp)

Verified with

• verify/tree/LC_vertex_add_subtree_sum.test.cpp

Code

#pragma once

template <class G>
pair<vector<int>, vector<int>> EulerTour(const G& g, int root = 0) {
  int n = g.size();
  assert(n > 0);
  assert(0 <= root && root < n);
  vector<int> in_time(n), out_time(n);
  vector<int> parent(n, -2), iter(n);
  parent[root] = -1;
  int t = 0;
  vector<int> st = {root};
  while (!st.empty()) {
    int x = st.back();
    if (iter[x] == 0) in_time[x] = t++;
    if (iter[x] == (int)g[x].size()) {
      out_time[x] = t;
      st.pop_back();
      continue;
    }
    int y = g[x][iter[x]++].to;
    if (y == parent[x]) continue;
    assert(parent[y] == -2);
    parent[y] = x;
    st.push_back(y);
  }
  assert(t == n);
  return {in_time, out_time};
}

/**
 * @brief Euler Tour of Tree
 * @docs docs/tree/euler-tour.md
 */

#line 2 "tree/euler-tour.hpp"

template <class G>
pair<vector<int>, vector<int>> EulerTour(const G& g, int root = 0) {
  int n = g.size();
  assert(n > 0);
  assert(0 <= root && root < n);
  vector<int> in_time(n), out_time(n);
  vector<int> parent(n, -2), iter(n);
  parent[root] = -1;
  int t = 0;
  vector<int> st = {root};
  while (!st.empty()) {
    int x = st.back();
    if (iter[x] == 0) in_time[x] = t++;
    if (iter[x] == (int)g[x].size()) {
      out_time[x] = t;
      st.pop_back();
      continue;
    }
    int y = g[x][iter[x]++].to;
    if (y == parent[x]) continue;
    assert(parent[y] == -2);
    parent[y] = x;
    st.push_back(y);
  }
  assert(t == n);
  return {in_time, out_time};
}

/**
 * @brief Euler Tour of Tree
 * @docs docs/tree/euler-tour.md
 */

Back to top page