lib/euler_tour.hpp

• View this file on GitHub
• Last update: 2020-05-09 20:29:45+09:00
• Include: #include "lib/euler_tour.hpp"

Verified with

• test/euler_tour.aoj.GRL_5_D.test.cpp

Code

#ifndef CPLIB_LIB_EULER_TOUR_H_
#define CPLIB_LIB_EULER_TOUR_H_

#include <vector>

// Vertex ver.
struct EulerTourV {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> left, right;

    // A range [left[i], right[i]) corresponds to a subtree from a vertex i
    EulerTourV(const Edge &edg, int root) : left(edg.size()), right(edg.size()) {
        int n = 0;
        dfs(edg, root, n);
    }

private:
    void dfs(const Edge &edg, int pos, int &id, int prev = -1) {
        left[pos] = id++;
        for (int c : edg[pos]) {
            if (c == prev) continue;
            dfs(edg, c, id, pos);
        }
        right[pos] = id;
    }
};

// Edge ver.
struct EulerTourE {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> left, right;

    // A range [left[i], right[i]) corresponds to a subtree from a vertex i
    EulerTourE(const Edge &edg, int root) : left(edg.size()), right(edg.size()) {
        int n = 0;
        dfs(edg, root, n);
    }

private:
    void dfs(const Edge &edg, int pos, int &id, int prev = -1) {
        left[pos] = id++;
        for (int c : edg[pos]) {
            if (c == prev) continue;
            dfs(edg, c, id, pos);
        }
        right[pos] = id++;
    }
};

#endif  // CPLIB_LIB_EULER_TOUR_H_

#line 1 "lib/euler_tour.hpp"



#include <vector>

// Vertex ver.
struct EulerTourV {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> left, right;

    // A range [left[i], right[i]) corresponds to a subtree from a vertex i
    EulerTourV(const Edge &edg, int root) : left(edg.size()), right(edg.size()) {
        int n = 0;
        dfs(edg, root, n);
    }

private:
    void dfs(const Edge &edg, int pos, int &id, int prev = -1) {
        left[pos] = id++;
        for (int c : edg[pos]) {
            if (c == prev) continue;
            dfs(edg, c, id, pos);
        }
        right[pos] = id;
    }
};

// Edge ver.
struct EulerTourE {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> left, right;

    // A range [left[i], right[i]) corresponds to a subtree from a vertex i
    EulerTourE(const Edge &edg, int root) : left(edg.size()), right(edg.size()) {
        int n = 0;
        dfs(edg, root, n);
    }

private:
    void dfs(const Edge &edg, int pos, int &id, int prev = -1) {
        left[pos] = id++;
        for (int c : edg[pos]) {
            if (c == prev) continue;
            dfs(edg, c, id, pos);
        }
        right[pos] = id++;
    }
};

Back to top page