meow::DisjointSet Class Reference

用來維護一堆互斥集的資訊 More...

#include "DisjointSet.h"

Public Member Functions
	DisjointSet ()
	constructor More...
	DisjointSet (size_t n)
	constructor More...
	DisjointSet (DisjointSet const &dsj)
	constructor More...
size_t	root (size_t a) const
	回傳指定的number所在的 集合的編號 More...
size_t	size () const
	回傳總element數 More...
void	reset (size_t n)
	重設 More...
size_t	merge (size_t a, size_t b)
	合併 More...

Detailed Description

用來維護一堆互斥集的資訊

DisjointSet 是個 輕量級Data Dtructure, 用來維護一堆互斥集的資訊.
相關資料可參考 演算法筆記

Note

• 時間複雜度 非常快 表示它真的算的超級快, 可以視為常數時間
• 預設值所有 number 所在的集合的編號就是 number 本身, 即沒有任兩個數在同一個set裡面

Author

cat_leopard

Constructor & Destructor Documentation

meow::DisjointSet::DisjointSet ( )

inline

constructor

meow::DisjointSet::DisjointSet ( size_t  n )

inline

constructor

Parameters

[in]

n

elements數

meow::DisjointSet::DisjointSet ( DisjointSet const &  dsj )

inline

constructor

將另一個 DisjointSet 原封不動的複製過來

Parameters

[in]

dsj

另一個 DisjointSet

Member Function Documentation

size_t meow::DisjointSet::merge ( size_t  a, size_t  b  )

inline

合併

將 number1 所在的集合 跟 number2 所在的集合 合併, 並回傳合併後新的集合的編號.
時間複雜度非常快

Parameters

[in]	a	即上述number1
[in]	b	即上述number2

Returns

新的編號

void meow::DisjointSet::reset ( size_t  n )

inline

重設

清空, 並且設定總集合大小為 n

Parameters

[in]

n

重新設定的集合大小 n

Returns

無

size_t meow::DisjointSet::root ( size_t  a ) const

inline

回傳指定的number所在的 集合的編號

時間複雜度 超級快

Parameters

[in]

a

指定的number

Returns

集合的編號

size_t meow::DisjointSet::size ( ) const

inline

回傳總element數

Returns

總element數

---

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

• meowpp/dsa/DisjointSet.h