DsuPotentialized< Group > 構造体テンプレート

ポテンシャル付き DSU [詳解]

#include "dsu_potentialized.hpp"

公開型
using	Type = typename Group::Type

公開メンバ関数
	DsuPotentialized ()=default
	DsuPotentialized (int n)
	コンストラクタ
int	find (int x)
	頂点 x を含む連結成分の代表元を返す
bool	merge (int x, int y, Type w)
	頂点　x と y を連結し、weight(x) = op(weight(y), w) とする
Type	weight (int x)
	頂点 x のポテンシャルを返す
Type	diff (int x, int y)
	op(inv(weight(y)), weight(x)) (x と y の間のポテンシャル差)を返す
int	size (int x)
	頂点 x を含む連結成分のサイズを返す
bool	same (int x, int y)
	頂点 x と y が同じ連結成分に属するか否かを返す
int	count ()
	連結成分の個数を返す
vector< vector< int > >	groups ()
	各頂点を連結成分に分解する

詳解

template<typename Group>
struct DsuPotentialized< Group >

ポテンシャル付き DSU

テンプレート引数

Group

群

dsu_potentialized.hpp の 6 行目に定義があります。

型定義メンバ詳解

Type

template<typename Group>

using DsuPotentialized< Group >::Type = typename Group::Type

dsu_potentialized.hpp の 7 行目に定義があります。

構築子と解体子

DsuPotentialized() [1/2]

template<typename Group>

DsuPotentialized< Group >::DsuPotentialized ( )

default

DsuPotentialized() [2/2]

template<typename Group>

DsuPotentialized< Group >::DsuPotentialized ( int n )

inline

コンストラクタ

dsu_potentialized.hpp の 11 行目に定義があります。

関数詳解

find()

template<typename Group>

int DsuPotentialized< Group >::find ( int x )

inline

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

dsu_potentialized.hpp の 19 行目に定義があります。

merge()

template<typename Group>

bool DsuPotentialized< Group >::merge ( int x, int y, Type w )

inline

頂点　x と y を連結し、weight(x) = op(weight(y), w) とする

dsu_potentialized.hpp の 27 行目に定義があります。

参照先 find(), weight().

weight()

template<typename Group>

Type DsuPotentialized< Group >::weight ( int x )

inline

頂点 x のポテンシャルを返す

dsu_potentialized.hpp の 41 行目に定義があります。

参照先 find().

diff()

template<typename Group>

Type DsuPotentialized< Group >::diff ( int x, int y )

inline

op(inv(weight(y)), weight(x)) (x と y の間のポテンシャル差)を返す

dsu_potentialized.hpp の 47 行目に定義があります。

size()

template<typename Group>

int DsuPotentialized< Group >::size ( int x )

inline

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

dsu_potentialized.hpp の 50 行目に定義があります。

same()

template<typename Group>

bool DsuPotentialized< Group >::same ( int x, int y )

inline

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

dsu_potentialized.hpp の 53 行目に定義があります。

参照先 find().

count()

template<typename Group>

int DsuPotentialized< Group >::count ( )

inline

連結成分の個数を返す

dsu_potentialized.hpp の 56 行目に定義があります。

groups()

template<typename Group>

vector< vector< int > > DsuPotentialized< Group >::groups ( )

inline

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

dsu_potentialized.hpp の 59 行目に定義があります。

---

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

• graph/dsu_potentialized.hpp