rm::UnionFind< Tp > 模板类 参考

并查集 更多...

#include <rmvl/algorithm/datastruct.hpp>

rm::UnionFind< Tp > 的协作图:

Public 类型
typedef Tp	value_type
typedef Tp &	reference
typedef const Tp &	const_reference
typedef std::size_t	size_type

Public 成员函数
template<typename InputIterator>
	UnionFind (InputIterator first, InputIterator last)
	构造并查集
	UnionFind (std::ranges::range auto &&range)
	构造并查集
bool	connected (const Tp &val_a, const Tp &val_b)
	两个元素是否在同一个集合
void	merge (const Tp &val_a, const Tp &val_b)
	将两个元素所在集合合并
std::unordered_map< Tp, std::vector< Tp > >	extract ()
	导出数据
int	components ()
	获取连通分量

Protected 成员函数
Tp	findRep (Tp element)
	寻找代表元素

Protected 属性
std::unordered_set< Tp >	_element_set
	元素集合
std::unordered_map< Tp, Tp >	_parent_map
	父元素哈希表
std::unordered_map< Tp, std::size_t >	_size_map
	集合大小
int	_connected_component {}
	连通分量

详细描述

template<typename Tp>
class rm::UnionFind< Tp >

并查集

模板参数

Tp

元素类型

成员类型定义说明

const_reference

template<typename Tp>

typedef const Tp& rm::UnionFind< Tp >::const_reference

reference

template<typename Tp>

typedef Tp& rm::UnionFind< Tp >::reference

size_type

template<typename Tp>

typedef std::size_t rm::UnionFind< Tp >::size_type

value_type

template<typename Tp>

typedef Tp rm::UnionFind< Tp >::value_type

构造及析构函数说明

UnionFind() [1/2]

template<typename Tp>

template<typename InputIterator>

rm::UnionFind< Tp >::UnionFind ( InputIterator first, InputIterator last )

inline

构造并查集

模板参数

InputIterator

老式前向迭代器类型

参数

[in]	first	起始迭代器
[in]	last	终止迭代器

UnionFind() [2/2]

template<typename Tp>

rm::UnionFind< Tp >::UnionFind ( std::ranges::range auto && range )

inline

构造并查集

参数

[in]

range

支持范围 for 的容器

函数调用图:

成员函数说明

components()

template<typename Tp>

int rm::UnionFind< Tp >::components ( )

inline

获取连通分量

connected()

template<typename Tp>

bool rm::UnionFind< Tp >::connected ( const Tp & val_a, const Tp & val_b )

inline

两个元素是否在同一个集合

参数

[in]	val_a	元素 A
[in]	val_b	元素 B

返回

是否在同一个集合

函数调用图:

extract()

template<typename Tp>

std::unordered_map< Tp, std::vector< Tp > > rm::UnionFind< Tp >::extract ( )

inline

导出数据

返回

Key: 集合代表元素，Value: 集合

函数调用图:

findRep()

template<typename Tp>

Tp rm::UnionFind< Tp >::findRep ( Tp element )

inlineprotected

寻找代表元素

merge()

template<typename Tp>

void rm::UnionFind< Tp >::merge ( const Tp & val_a, const Tp & val_b )

inline

将两个元素所在集合合并

参数

[in]	val_a	元素 A
[in]	val_b	元素 B

函数调用图:

类成员变量说明

_connected_component

template<typename Tp>

int rm::UnionFind< Tp >::_connected_component {}

protected

连通分量

_element_set

template<typename Tp>

std::unordered_set<Tp> rm::UnionFind< Tp >::_element_set

protected

元素集合

_parent_map

template<typename Tp>

std::unordered_map<Tp, Tp> rm::UnionFind< Tp >::_parent_map

protected

父元素哈希表

_size_map

template<typename Tp>

std::unordered_map<Tp, std::size_t> rm::UnionFind< Tp >::_size_map

protected

集合大小