This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "graph/tree_diameter.hpp"
auto [d, path] = tree_diameter(G);
d
path
#pragma once #include "graph/graph_template.hpp" template <class T> std::pair<T, std::vector<Edge<T>>> tree_diameter(Graph<T> &G) { std::vector<int> to(G.size(), -1); auto dfs = [&](auto f, int cur, int par) -> std::pair<T, int> { std::pair<T, int> ret = {0, cur}; for (auto &e : G[cur]) { if (e.to == par) continue; auto cost = f(f, e.to, cur); cost.first += e.cost; if (ret.first < cost.first) { ret = cost; to[cur] = e.to; } } return ret; }; auto s = dfs(dfs, 0, -1); auto t = dfs(dfs, s.second, -1); int cur = s.second; std::vector<Edge<T>> path; while (cur != t.second) { for (auto &e : G[cur]) { if (to[cur] == e.to) { path.emplace_back(e); } } cur = to[cur]; } return {t.first, path}; }
#line 2 "graph/tree_diameter.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/tree_diameter.hpp" template <class T> std::pair<T, std::vector<Edge<T>>> tree_diameter(Graph<T> &G) { std::vector<int> to(G.size(), -1); auto dfs = [&](auto f, int cur, int par) -> std::pair<T, int> { std::pair<T, int> ret = {0, cur}; for (auto &e : G[cur]) { if (e.to == par) continue; auto cost = f(f, e.to, cur); cost.first += e.cost; if (ret.first < cost.first) { ret = cost; to[cur] = e.to; } } return ret; }; auto s = dfs(dfs, 0, -1); auto t = dfs(dfs, s.second, -1); int cur = s.second; std::vector<Edge<T>> path; while (cur != t.second) { for (auto &e : G[cur]) { if (to[cur] == e.to) { path.emplace_back(e); } } cur = to[cur]; } return {t.first, path}; }