用途
木の直径を求める.
計算量
$ O(n) $
Depends
使い方
宣言
1
| auto res = getGraphDiameter(g,s);
|
res.costで直径を得る. res.u, res.vで直径を結ぶ頂点を得る.
実装
1
2
3
4
5
6
7
8
| struct getGraphDiameter_return {
int u, v, cost;
};
getGraphDiameter_return getGraphDiameter(DirectedGraph &_g) {
auto u = getFarthestVertex(_g, 0);
auto v = getFarthestVertex(_g, u.v);
return {u.v, v.v, v.cost};
}
|
Verify👍
https://atcoder.jp/contests/typical90/submissions/57586680