木の直径(tree-diameter)
目的
木(N頂点N-1辺であり、各頂点に必ずアクセスできるグラフ)の直径を求める。 直径とはグラフの最遠距離である。
関数
build( ): 木の直径を返す。path には直径を構成する辺が格納される。
コード
template< typename T = int > struct TreeDiameter : Graph< T > { public: using Graph< T >::Graph; using Graph< T >::g; vector< Edge< T > > path; T build() { to.assign(g.size(), -1); auto p = dfs(0, -1); auto q = dfs(p.second, -1); int now = p.second; while(now != q.second) { for(auto &e : g[now]) { if(to[now] == e.to) { path.emplace_back(e); } } now = to[now]; } return q.first; } explicit TreeDiameter(const Graph< T > &g) : Graph< T >(g) {} private: vector< int > to; pair< T, int > dfs(int idx, int par) { pair< T, int > ret(0, idx); for(auto &e : g[idx]) { if(e.to == par) continue; auto cost = dfs(e.to, idx); cost.first += e.cost; if(ret < cost) { ret = cost; to[idx] = e.to; } } return ret; } };
コードテスト
https://judge.yosupo.jp/problem/tree_diameter
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define REP(i, x) for (ll i = 0; i < (ll)(x); i++) #define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++) #define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--) #define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--) #define all(x) (x).begin(), (x).end() //-------グラフテンプレ------- template <typename T = int> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template <typename T = int> struct Graph { vector<vector<Edge<T>>> g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if (weighted) cin >> c; if (directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } }; template <typename T = int> using Edges = vector<Edge<T>>; //-------グラフテンプレここまで------- template <typename T = int> struct TreeDiameter : Graph<T> { public: using Graph<T>::Graph; using Graph<T>::g; vector<Edge<T>> path; T build() { to.assign(g.size(), -1); auto p = dfs(0, -1); auto q = dfs(p.second, -1); int now = p.second; while (now != q.second) { for (auto &e : g[now]) { if (to[now] == e.to) { path.emplace_back(e); } } now = to[now]; } return q.first; } explicit TreeDiameter(const Graph<T> &g) : Graph<T>(g) {} private: vector<int> to; pair<T, int> dfs(int idx, int par) { pair<T, int> ret(0, idx); for (auto &e : g[idx]) { if (e.to == par) continue; auto cost = dfs(e.to, idx); cost.first += e.cost; if (ret < cost) { ret = cost; to[idx] = e.to; } } return ret; } }; int main() { int N; cin >> N; TreeDiameter<int64_t> g(N); g.read(N - 1, 0, true); //グラフ読み込み cout << g.build() << " "; //木の直径(重み付き最遠距離) cout << g.path.size() + 1 << "\n"; //辺の数+1=頂点の数 REP(i, g.path.size()) { cout << g.path[i].from << " "; //辺の始点と終点、from有りで始点、無しで終点 } cout << g.path[g.path.size() - 1] << endl; //最終の終点を出力 }