This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "graph/euler_tour.hpp"
#pragma once #include "graph/graph_template.hpp" // Euler Tour // complexity: O(N + M) // N = 5 // edges = [{0, 1}, {0, 2}, {2, 3}, {2, 4}] // 0 // / \ // 1 2 // / \ // 3 4 // vertices = [0, 1, 0, 2, 3, 2, 4, 2, 0] // vertex_id = [{0, 8}, {1, 1}, {3, 7}, {4, 4}, {6, 6}] // edges = [0, 0+N, 1, 2, 2+N, 3, 3+N, 1+N] // edge_id = [{0, 1}, {2, 7}, {3, 4}, {5, 6}] // edges[vertex_id[i].first, vertex_id[i].second) = edges in subtree with root i template <class T> std::tuple<std::vector<int>, std::vector<std::pair<int, int>>, std::vector<int>, std::vector<std::pair<int, int>>> // euler_tour(Graph<T> &G, int root = 0) { // compiler bugs // const int n = (int)G.size(); // fix int n = (int)G.size(); std::vector<int> vertices, edges; std::vector<std::pair<int, int>> vertex_id(n), edge_id(n - 1); vertices.reserve(2 * n - 1); edges.reserve(2 * (n - 1)); auto dfs = [&](auto f, int cur, int par) -> void { vertex_id[cur].first = (int)vertices.size(); vertices.push_back(cur); for (auto &&e : G[cur]) { if (e.to == par) continue; edge_id[e.id].first = (int)edges.size(); edges.push_back(e.id); f(f, e.to, cur); vertices.push_back(cur); edge_id[e.id].second = (int)edges.size(); edges.push_back(e.id + n); } vertex_id[cur].second = (int)vertices.size() - 1; }; dfs(dfs, root, -1); assert((int)vertices.size() == 2 * n - 1); assert((int)edges.size() == 2 * (n - 1)); return {vertices, vertex_id, edges, edge_id}; }
#line 2 "graph/euler_tour.hpp" #line 2 "graph/graph_template.hpp" #include <vector> template <class T> struct Edge { int from, to; T cost; int id; Edge() = default; Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {} friend std::ostream &operator<<(std::ostream &os, const Edge<T> &e) { // output format: "{ id : from -> to, cost }" return os << "{ " << e.id << " : " << e.from << " -> " << e.to << ", " << e.cost << " }"; } }; template <class T> using Edges = std::vector<Edge<T>>; template <class T> using Graph = std::vector<std::vector<Edge<T>>>; #line 4 "graph/euler_tour.hpp" // Euler Tour // complexity: O(N + M) // N = 5 // edges = [{0, 1}, {0, 2}, {2, 3}, {2, 4}] // 0 // / \ // 1 2 // / \ // 3 4 // vertices = [0, 1, 0, 2, 3, 2, 4, 2, 0] // vertex_id = [{0, 8}, {1, 1}, {3, 7}, {4, 4}, {6, 6}] // edges = [0, 0+N, 1, 2, 2+N, 3, 3+N, 1+N] // edge_id = [{0, 1}, {2, 7}, {3, 4}, {5, 6}] // edges[vertex_id[i].first, vertex_id[i].second) = edges in subtree with root i template <class T> std::tuple<std::vector<int>, std::vector<std::pair<int, int>>, std::vector<int>, std::vector<std::pair<int, int>>> // euler_tour(Graph<T> &G, int root = 0) { // compiler bugs // const int n = (int)G.size(); // fix int n = (int)G.size(); std::vector<int> vertices, edges; std::vector<std::pair<int, int>> vertex_id(n), edge_id(n - 1); vertices.reserve(2 * n - 1); edges.reserve(2 * (n - 1)); auto dfs = [&](auto f, int cur, int par) -> void { vertex_id[cur].first = (int)vertices.size(); vertices.push_back(cur); for (auto &&e : G[cur]) { if (e.to == par) continue; edge_id[e.id].first = (int)edges.size(); edges.push_back(e.id); f(f, e.to, cur); vertices.push_back(cur); edge_id[e.id].second = (int)edges.size(); edges.push_back(e.id + n); } vertex_id[cur].second = (int)vertices.size() - 1; }; dfs(dfs, root, -1); assert((int)vertices.size() == 2 * n - 1); assert((int)edges.size() == 2 * (n - 1)); return {vertices, vertex_id, edges, edge_id}; }