getGraphDiameter(木の直径を求める)
romophic-library
用途
木の直径を求める.
計算量
$ O(n) $
Depends
使い方
宣言
auto res = getGraphDiameter(g,s);
res.costで直径を得る. res.u, res.vで直径を結ぶ頂点を得る.
実装
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};
}