木の直径

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/tree/tree-diameter.hpp

主な機能

$n$ 頂点の木の隣接リスト表現を CsrArray<int> で入力すると、木の直径であるパスを $1$ つ求める。

関数

UnitTreeDiameter

std::vector<int> UnitTreeDiameter(const Graph& T);
std::vector<int> UnitTreeDiameter(const CsrArray<int>& T);

nachia::Graph とは？

nachia::CsrArray とは？

• 頂点数 $n$ : $1 \leq n \leq 10^8$
• $O(n)$ 時間

木の直径のパスを表す頂点列を求める。

木は nachia::Graph で与えるほか、隣接頂点のリストを表す nachia::CsrArray<int> で与えてもよい。

---

TOP PAGE