オイラーツアー
Last updated：2018-04-16 03:25:49
Tweet
Category:木,
Tag：
オイラーツアー
概要
木をDFSしたときの頂点番号を訪問順で記録した列を作る.
これとセグ木などを合わせて用いることで部分木に対するクエリを高速に処理できることがある.
計算量
DFSで$O(|V|+|E|)$.
使い方
作成済みの木gとその根をコンストラクタに渡してやることで，次のメンバを使うことが出来る:
eulerTour: DFS訪問順に並べた頂点番号begin:begin[v]でeulerTour内で最も左の頂点$v$の添え字番号を返すend:end[v]でeulerTour内で最も右のの頂点$v$の添え字番号+1を返す
(endで+1しているのは$[begin, end)$と半開区間にしたため)
// 木を作る
std::vector<std::vector<int>> g(n);
REP(i, m) {
g[a[i]].emplace_back(b[i]);
g[b[i]].emplace_back(a[i]);
}
// オイラーツアーを行う
int root = 0;
EulerTour et(g, root);
実装例