DsuRollback 構造体

ロールバック可能DSU [詳解]

#include "dsu_rollback.hpp"

公開メンバ関数
	DsuRollback ()=default
	DsuRollback (int n)
	コンストラクタ
int	find (int x)
	頂点 x を含む連結成分の代表元を返す
bool	merge (int x, int y)
	頂点 x と y を連結し、true を返す
void	undo ()
	最後に行った連結操作を取り消す
void	snapshot ()
	DSUの状態を上書き保存する
void	rollback ()
	最後に snapshot した時点まで巻き戻す
int	size (int x)
	頂点 x を含む連結成分のサイズを返す
bool	same (int x, int y)
	頂点 x と y が同じ連結成分に属するか否かを返す
int	count ()
	連結成分の個数を返す
vector< vector< int > >	groups ()
	各頂点を連結成分に分解する

詳解

ロールバック可能DSU

dsu_rollback.hpp の 5 行目に定義があります。

構築子と解体子

DsuRollback() [1/2]

DsuRollback::DsuRollback ( )

default

DsuRollback() [2/2]

DsuRollback::DsuRollback ( int n )

inline

コンストラクタ

dsu_rollback.hpp の 9 行目に定義があります。

関数詳解

find()

int DsuRollback::find ( int x )

inline

頂点 x を含む連結成分の代表元を返す

dsu_rollback.hpp の 16 行目に定義があります。

merge()

bool DsuRollback::merge ( int x, int y )

inline

頂点 x と y を連結し、true を返す

既に連結されている場合は false を返す

dsu_rollback.hpp の 23 行目に定義があります。

参照先 find().

undo()

void DsuRollback::undo ( )

inline

最後に行った連結操作を取り消す

dsu_rollback.hpp の 37 行目に定義があります。

snapshot()

void DsuRollback::snapshot ( )

inline

DSUの状態を上書き保存する

dsu_rollback.hpp の 46 行目に定義があります。

rollback()

void DsuRollback::rollback ( )

inline

最後に snapshot した時点まで巻き戻す

dsu_rollback.hpp の 49 行目に定義があります。

参照先 undo().

size()

int DsuRollback::size ( int x )

inline

頂点 x を含む連結成分のサイズを返す

dsu_rollback.hpp の 52 行目に定義があります。

same()

bool DsuRollback::same ( int x, int y )

inline

頂点 x と y が同じ連結成分に属するか否かを返す

dsu_rollback.hpp の 55 行目に定義があります。

参照先 find().

count()

int DsuRollback::count ( )

inline

連結成分の個数を返す

dsu_rollback.hpp の 58 行目に定義があります。

groups()

vector< vector< int > > DsuRollback::groups ( )

inline

各頂点を連結成分に分解する

dsu_rollback.hpp の 61 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• graph/dsu_rollback.hpp