Euler Tour
(tree/euler_tour.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "tree/euler_tour.hpp"

Verified with

• test/yosupo/vertex_add_subtree_sum.euler_tour.test.cpp

Code

#pragma once
#include <vector>

/**
 * @brief Euler Tour
 */
std::pair<std::vector<int>, std::vector<int>> euler_tour(
    const std::vector<std::vector<int>>& G, int root) {
    std::vector<int> in(G.size()), out(G.size());
    int k = 0;

    auto dfs = [&](auto& dfs, int v, int p) -> void {
        in[v] = k++;
        for (int c : G[v])
            if (c != p) dfs(dfs, c, v);
        out[v] = k;
    };

    dfs(dfs, root, -1);
    return {in, out};
}

#line 2 "tree/euler_tour.hpp"
#include <vector>

/**
 * @brief Euler Tour
 */
std::pair<std::vector<int>, std::vector<int>> euler_tour(
    const std::vector<std::vector<int>>& G, int root) {
    std::vector<int> in(G.size()), out(G.size());
    int k = 0;

    auto dfs = [&](auto& dfs, int v, int p) -> void {
        in[v] = k++;
        for (int c : G[v])
            if (c != p) dfs(dfs, c, v);
        out[v] = k;
    };

    dfs(dfs, root, -1);
    return {in, out};
}

Back to top page