competitive-programming-library

This documentation is automatically generated by online-judge-verify-helper

View the Project on GitHub kmyk/competitive-programming-library

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

Back to top page

Required by

Verified with

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