DSU 構造体

Disjoint Set Union [詳解]

#include "dsu.hpp"

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

詳解

Disjoint Set Union

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

構築子と解体子

DSU() [1/2]

DSU::DSU ( )

default

DSU() [2/2]

DSU::DSU ( int n )

inline

コンストラクタ

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

関数詳解

find()

int DSU::find ( int x )

inline

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

覚え書き

O(α(N))

dsu.hpp の 17 行目に定義があります。

merge()

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

inline

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

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

覚え書き

O(α(N))

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

参照先 find().

size()

int DSU::size ( int x )

inline

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

覚え書き

O(α(N))

dsu.hpp の 36 行目に定義があります。

same()

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

inline

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

覚え書き

O(α(N))

dsu.hpp の 40 行目に定義があります。

参照先 find().

count()

int DSU::count ( )

inline

連結成分の個数を返す

覚え書き

O(1)

dsu.hpp の 44 行目に定義があります。

groups()

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

inline

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

覚え書き

O(N)

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

---

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

• graph/dsu.hpp