木の周遊路 (Euler Tour)

概要

木を根から深さ優先探索し，通った順の列を返します．この列は部分木が連続した区間になるという良い性質を持つため，セグメント木を用いて部分木やパスに対するクエリを処理したりできます．

使い方

子→親方向の辺が存在しない前提の実装．

計算量

$O(V)$

実装

Graph to_rooted(const Graph &g, int r = 0) {
    int n = g.size();
    Graph ng(n);
    std::vector<int> ord(n, -1);
    std::queue<int> q;
    q.push(r);
    int k = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (auto &e : g[u]) {
            int v = e.dst;
            if (ord[v] == -1) {
                ord[v] = k++;
                q.push(v);
                ng[u].emplace_back(e);
            }
        }
    }
    return ng;
}

std::vector<int> eulerTour(Graph g, int r = 0) {
    g = to_rooted(g, r);
    std::vector<int> vs;
    std::vector<int> s = {r};
    std::vector<size_t> vis(g.size());
    while (s.size()) {
        int v = s.back();
        vis[v]++;
        vs.push_back(v);
        if (vis[v] == g[v].size() + 1) {
            s.pop_back();
            continue;
        } else
            s.push_back(g[v][vis[v] - 1].dst);
    }
    return vs;
}