Euler Tour (preorder)
(graph/euler_tour_preorder.hpp)

• View this file on GitHub
• Last update: 2020-02-26 19:51:56+09:00
• Include: #include "graph/euler_tour_preorder.hpp"

Required by

• Euler Tour (subtree queries, with commutative monoids) (data_structure/euler_tour_subtree_query.hpp)
• 虚樹 / virtual trees (graph/virtual_trees.hpp)

Verified with

• data_structure/euler_tour_subtree_query.vertex_add_subtree_sum.test.cpp

Code

#pragma once
#include <functional>
#include <vector>

/**
 * @brief Euler Tour (preorder)
 * @arg g must be a rooted tree, directed or undirected
 */
void do_euler_tour_preorder(std::vector<std::vector<int> > const & g, int root, std::vector<int> & tour, std::vector<int> & left, std::vector<int> & right) {
    int n = g.size();
    tour.clear();
    left.assign(n, -1);
    right.assign(n, -1);
    std::function<void (int, int)> go = [&](int x, int parent) {
        left[x] = tour.size();
        tour.push_back(x);
        for (int y : g[x]) if (y != parent) {
            go(y, x);
        }
        right[x] = tour.size();
    };
    go(root, -1);
}

#line 2 "graph/euler_tour_preorder.hpp"
#include <functional>
#include <vector>

/**
 * @brief Euler Tour (preorder)
 * @arg g must be a rooted tree, directed or undirected
 */
void do_euler_tour_preorder(std::vector<std::vector<int> > const & g, int root, std::vector<int> & tour, std::vector<int> & left, std::vector<int> & right) {
    int n = g.size();
    tour.clear();
    left.assign(n, -1);
    right.assign(n, -1);
    std::function<void (int, int)> go = [&](int x, int parent) {
        left[x] = tour.size();
        tour.push_back(x);
        for (int y : g[x]) if (y != parent) {
            go(y, x);
        }
        right[x] = tour.size();
    };
    go(root, -1);
}

Back to top page