木の重心

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

ソースコード

nachia/tree/tree-centroid.hpp

主な機能

$n$ 頂点の木の隣接リスト表現を CsrArray<int> で入力すると、木の重心を求める。

ここで木の重心とは、その頂点で木を分割したとき各成分の頂点数が高々 $\frac{n}{2}$ となるおうな頂点である。

$n$ が奇数なら $1$ つの頂点番号を、偶数なら $2$ つの頂点番号を返す。

関数

UnitTreeCentroid

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

nachia::Graph とは？

nachia::CsrArray とは？

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

木の重心をすべて求める。

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

---

TOP PAGE