Online Dynamic Connectivity
ソースコード
nachia/graph/dynamic-connectivity.hpp
主な機能
fully-dynamic connectivity problem をオンラインで解き、全域森を管理する。
頂点の番号は $0$ -based 。
struct OnlineFullyDynamicConnectivityBySplayEtt
コンストラクタ
OnlineFullyDynamicConnectivityBySplayEtt(int n);
- $1 \leq n \leq 3 \times 10^5$
- $O(n \log n)$ 時間
$n$ 頂点で辺を持たないグラフで、初期化する。
link
std::pair<int, int> link(int u, int v);
- $0 \leq u \lt n$
- $0 \leq v \lt n$
- この時点でグラフは辺 $\lbrace u,v \rbrace $ をもたない
- 償却 平均 $O( ( \log n ) ^2 )$ 時間
グラフに辺 $\lbrace u,v \rbrace $ を追加する。
全域森の辺を追加する必要がある場合はその辺の両端の頂点番号、それ以外の場合は $(-1,-1)$ を返す。
cut
ForestCutQuery cut(int u, int v);
- $0 \leq u \lt n$
- $0 \leq v \lt n$
- この時点でグラフは辺 $\lbrace u,v \rbrace $ をもつ
- 償却 平均 $O( ( \log n ) ^2 )$ 時間
グラフの辺 $\lbrace u,v \rbrace $ を削除する。
返り値は全域森における辺の削除 forest_cut と辺の追加 forest_link の組である。返り値を利用する場合、削除を先に行わなければならない。いずれも std::pair<int, int> 型。
全域森の辺を削除する必要がある場合は forest_cut はその辺の両端の頂点番号、それ以外の場合は $(-1,-1)$ を返す。
全域森の辺を追加する必要がある場合は forest_link はその辺の両端の頂点番号、それ以外の場合は $(-1,-1)$ を返す。
is_connected
bool is_connected(int u, int v);
- $0 \leq u \lt n$
- $0 \leq v \lt n$
- 償却 平均 $O( \log n )$ 時間
$2$ 頂点 $u$ , $v$ が連結であるなら true 、そうでなければ false を返す。
備考
現状 splay tree を用いているが、今後 randomized BST を用いるように変更するかもしれない。
参考[1] で紹介されている、名前がついているかどうかよく知らないアルゴリズムを使っている。このアルゴリズムは各連結成分の頂点数が小さいと高速に動作するが、一方で、例えば全域木 + α を構築してからその辺をすべて取り除くというような操作列では低速になる。 union-find やマージ過程を表す木を構築するなどで処理できる場合は、そのほうが何十倍も高速だろう。
参考
[1] hotman78 | online dynamic connectivity(削除可能union-find)の作り方を詳しく解説！！！ https://qiita.com/hotman78/items/78cd3aa50b05a57738d4