dsu_on_tree
クラス · DSU on Tree
template <graph_type G>
struct dsu_on_tree;
概要
DSU on Tree
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
G |
グラフ型（list_graph<T> / csr_graph<T> のいずれでも可） |
計算量
- 前処理 $O(n+q)$、solveはcallback呼出し $O((n+q)\log n)$ 回
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 頂点ごとのquery列に対するDSU on Tree順序を構築する (2) 各頂点を1queryとしたDSU on Tree順序を構築する |
(1) $O(n+q)$ (2) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
solve |
query追加・頂点回答・状態clearのcallbackで全頂点を処理する | callback呼出し $O((n+q)\log n)$ 回 |
メンバの詳細
(constructor)
// (1)
dsu_on_tree(const G &_g, const std::vector<int> &query, int r = 0);
// (2)
dsu_on_tree(const G &_g, int r = 0);
(1) 頂点ごとのquery列に対するDSU on Tree順序を構築する
- 計算量: $O(n+q)$
(2) 各頂点を1queryとしたDSU on Tree順序を構築する
- 計算量: $O(n)$