DsuMerging< Semigroup > 構造体テンプレート

値をマージする DSU [詳解]

#include "dsu_merging.hpp"

公開型
using	Type = typename Semigroup::Type

公開メンバ関数
	DsuMerging ()=default
	DsuMerging (int n, const vector< Type > &v)
	コンストラクタ
int	find (int x)
	頂点 x を含む連結成分の代表元を返す
bool	merge (int x, int y)
	頂点 x と y を連結し、true を返す
const Type &	get (int x)
	頂点 x を含む連結成分の半群積を返す
int	size (int x) const
	頂点 x を含む連結成分のサイズを返す
bool	same (int x, int y) const
	頂点 x と y が同じ連結成分に属するか否かを返す
int	count () const
	連結成分の個数を返す
vector< vector< int > >	groups () const
	各頂点を連結成分に分解する

詳解

template<typename Semigroup = DsuBaseSemigroup>
struct DsuMerging< Semigroup >

値をマージする DSU

テンプレート引数

Semigroup

半群

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

型定義メンバ詳解

Type

template<typename Semigroup = DsuBaseSemigroup>

using DsuMerging< Semigroup >::Type = typename Semigroup::Type

dsu_merging.hpp の 12 行目に定義があります。

構築子と解体子

DsuMerging() [1/2]

template<typename Semigroup = DsuBaseSemigroup>

DsuMerging< Semigroup >::DsuMerging ( )

default

DsuMerging() [2/2]

template<typename Semigroup = DsuBaseSemigroup>

DsuMerging< Semigroup >::DsuMerging ( int n, const vector< Type > & v )

inline

コンストラクタ

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

関数詳解

find()

template<typename Semigroup = DsuBaseSemigroup>

int DsuMerging< Semigroup >::find ( int x )

inline

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

覚え書き

O(α(N))

dsu_merging.hpp の 25 行目に定義があります。

merge()

template<typename Semigroup = DsuBaseSemigroup>

bool DsuMerging< Semigroup >::merge ( int x, int y )

inline

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

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

覚え書き

O(α(N))

dsu_merging.hpp の 33 行目に定義があります。

参照先 find().

get()

template<typename Semigroup = DsuBaseSemigroup>

const Type & DsuMerging< Semigroup >::get ( int x )

inline

頂点 x を含む連結成分の半群積を返す

dsu_merging.hpp の 48 行目に定義があります。

size()

template<typename Semigroup = DsuBaseSemigroup>

int DsuMerging< Semigroup >::size ( int x ) const

inline

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

dsu_merging.hpp の 51 行目に定義があります。

same()

template<typename Semigroup = DsuBaseSemigroup>

bool DsuMerging< Semigroup >::same ( int x, int y ) const

inline

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

dsu_merging.hpp の 54 行目に定義があります。

参照先 find().

count()

template<typename Semigroup = DsuBaseSemigroup>

int DsuMerging< Semigroup >::count ( ) const

inline

連結成分の個数を返す

dsu_merging.hpp の 57 行目に定義があります。

groups()

template<typename Semigroup = DsuBaseSemigroup>

vector< vector< int > > DsuMerging< Semigroup >::groups ( ) const

inline

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

dsu_merging.hpp の 60 行目に定義があります。

---

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

• graph/dsu_merging.hpp