centroid_decomposition
クラス · 重心分解
template <graph_type G>
struct centroid_decomposition;
概要
重心分解
木を重心で再帰的に分解する。重心分解木の親配列を保持し、run で 各重心ごとの集計コールバックを呼べる。 - 重心分解木の再帰は深さ $O(\log n)$ なので再帰で実装する。 - 連結成分の走査・部分木サイズ計算・距離計算は深さ $n$ になりうるため すべて BFS 反復で行い、鎖状の木でもスタックオーバーフローしない。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
G |
グラフ型（list_graph<T> / csr_graph<T> のいずれでも可。距離は辺数で数える） |
計算量
- 構築・全重心の走査は $O(n \log n)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
重心分解を実行する。 | $O(n\log n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
par |
重心分解木における各頂点の親（根は -1）。 | $O(1)$ |
run |
各重心ごとに集計コールバックを呼ぶ。 | callbackを除き $O(n\log n)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
component |
ある重心 c の回で渡される連結成分の情報。 |
参照用viewで実行時計算量はない |
メンバの詳細
(constructor)
explicit centroid_decomposition(const G &g);
重心分解を実行する。
- パラメータ
g: 木（無向辺で構築されていること） - 計算量: $O(n\log n)$
run
template <class F>
void run(F f);
各重心ごとに集計コールバックを呼ぶ。
分解木の根（全体の重心）から順に、各重心 c について f(component) を 1 回ずつ呼ぶ。component 内の配列は呼び出しごとに 使い回されるので、必要なら呼び出し中にコピーすること。
- パラメータ
f:void(const component &)互換の呼び出し可能オブジェクト - 計算量: callbackを除き $O(n\log n)$
component
struct component;
ある重心 c の回で渡される連結成分の情報。
いずれの配列も頂点番号で添字付けされる。order に現れない頂点 （別成分や used 済み）の成分は未定義なので参照しないこと。
- 計算量: 参照用viewで実行時計算量はない
関連項目
centroid_decomposition_par— 重心分解木の親配列だけを返す簡易版。