木の中心

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

ソースコード

nachia/tree/tree-center.hpp

主な機能

木を入力すると、木の中心を求める。

ここで木の中心とは、直径のパス上の中央単一の点あるいは辺である。

直径の頂点数が奇数なら $1$ つの頂点番号を、偶数なら辺の両端である $2$ つの頂点番号を返す。

関数

UnitTreeCenter

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

nachia::Graph とは？

nachia::CsrArray とは？

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

木の中心を求める。

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

---

TOP PAGE