s3d::DisjointSet< IndexType > Class Template Reference

Disjoint Set Union (Union-Find) More...

#include <DisjointSet.hpp>

Public Types
using	index_type = IndexType
	インデックスの型 More...
using	signed_index_type = std::make_signed_t< index_type >
	内部のインデックス型 More...

Public Member Functions
SIV3D_NODISCARD_CXX20	DisjointSet ()=default
	デフォルトコンストラクタ More...
SIV3D_NODISCARD_CXX20	DisjointSet (size_t n)
	要素数を指定して Disjoint Set Union を作成します。 More...
	operator bool () const noexcept
	要素を持つかを返します。 More...
bool	isEmpty () const noexcept
	要素が空であるかを返します。 More...
size_t	size () const noexcept
	要素数を返します。 More...
index_type	find (index_type i) noexcept
	ノード i を含むグループの root を返します。 More...
bool	connected (index_type i, index_type k) noexcept
	ノード i とノード k か同じグループに含まれているかを返します。 More...
bool	isRoot (index_type i) const noexcept
	ノード i がグループの root であるかを返します。 More...
bool	merge (index_type i, index_type k) noexcept
	ノード i を含むグループとノード k を含むグループを併合します。 More...
size_t	size (index_type i) noexcept
	ノード i を含むグループの要素数を返します。 More...
size_t	countSets () const noexcept
	グループの個数を返します。 More...
void	reset () noexcept
	グループ関係をすべて解消します。 More...

Static Public Attributes
static constexpr size_t	MaxSize = (static_cast<size_t>(std::numeric_limits<signed_index_type>::max()) + 1)
	現在のインデックスの型で保持可能な最大の要素数 More...

Detailed Description

template<class IndexType>
class s3d::DisjointSet< IndexType >

Disjoint Set Union (Union-Find)

Template Parameters

IndexType

インデックスの型

Member Typedef Documentation

index_type

template<class IndexType >

using s3d::DisjointSet< IndexType >::index_type = IndexType

インデックスの型

signed_index_type

template<class IndexType >

using s3d::DisjointSet< IndexType >::signed_index_type = std::make_signed_t<index_type>

内部のインデックス型

Constructor & Destructor Documentation

DisjointSet() [1/2]

template<class IndexType >

SIV3D_NODISCARD_CXX20 s3d::DisjointSet< IndexType >::DisjointSet ( )

default

デフォルトコンストラクタ

DisjointSet() [2/2]

template<class IndexType >

SIV3D_NODISCARD_CXX20 s3d::DisjointSet< IndexType >::DisjointSet ( size_t  n )

explicit

要素数を指定して Disjoint Set Union を作成します。

Parameters

n

要素数

Member Function Documentation

connected()

template<class IndexType >

bool s3d::DisjointSet< IndexType >::connected ( index_type  i, index_type  k  )

noexcept

ノード i とノード k か同じグループに含まれているかを返します。

Parameters

i	ノードのインデックス
k	ノードのインデックス

Returns

ノード i とノード k か同じグループに含まれている場合 true, それ以外の場合は false

countSets()

template<class IndexType >

size_t s3d::DisjointSet< IndexType >::countSets ( ) const

noexcept

グループの個数を返します。

Returns

グループの個数

find()

template<class IndexType >

index_type s3d::DisjointSet< IndexType >::find ( index_type  i )

noexcept

ノード i を含むグループの root を返します。

Parameters

i	ノードのインデックス

Returns

ノード i を含むグループの root

isEmpty()

template<class IndexType >

bool s3d::DisjointSet< IndexType >::isEmpty ( ) const

noexcept

要素が空であるかを返します。

Returns

要素数が 0 の場合は true, それ以外の場合は false

isRoot()

template<class IndexType >

bool s3d::DisjointSet< IndexType >::isRoot ( index_type  i ) const

noexcept

ノード i がグループの root であるかを返します。

Parameters

i	ノードのインデックス

Returns

ノード i がグループの root である場合 true, それ以外の場合は false

merge()

template<class IndexType >

bool s3d::DisjointSet< IndexType >::merge ( index_type  i, index_type  k  )

noexcept

ノード i を含むグループとノード k を含むグループを併合します。

Parameters

i	ノードのインデックス
k	ノードのインデックス

Returns

すでに両者が同じグループであった場合 false, それ以外の場合は true

operator bool()

template<class IndexType >

s3d::DisjointSet< IndexType >::operator bool ( ) const

explicitnoexcept

要素を持つかを返します。

Returns

要素数が 0 の場合は false, それ以外の場合は true

reset()

template<class IndexType >

void s3d::DisjointSet< IndexType >::reset ( )

noexcept

グループ関係をすべて解消します。

size() [1/2]

template<class IndexType >

size_t s3d::DisjointSet< IndexType >::size ( ) const

noexcept

要素数を返します。

Returns

要素数

size() [2/2]

template<class IndexType >

size_t s3d::DisjointSet< IndexType >::size ( index_type  i )

noexcept

ノード i を含むグループの要素数を返します。

Parameters

i	ノードのインデックス

Returns

ノード i を含むグループの要素数

Member Data Documentation

MaxSize

template<class IndexType >

constexpr size_t s3d::DisjointSet< IndexType >::MaxSize = (static_cast<size_t>(std::numeric_limits<signed_index_type>::max()) + 1)

staticconstexpr

現在のインデックスの型で保持可能な最大の要素数

Remarks

例えば、インデックス型が uint8 の場合は 128 個です。

---

The documentation for this class was generated from the following file:

• OpenSiv3D/Siv3D/include/Siv3D/DisjointSet.hpp