blob: b918adb90a043b6e3cd6d6817855a08bf17a34c6 (
plain) (
tree)
|
|
#ifndef DisjointSet_H__
#define DisjointSet_H__
#include <vector>
#include <cstdlib>
namespace meow{
//#
//#=== meow:: *DisjointSet* (C++ class)
//#==== Description
//# `DisjointSet` 是個*輕量級Data Dtructure*, 用來維護一堆互斥集的資訊.
//# 相關資料可參考
//# link:http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[演算法筆記]
//#
class DisjointSet{
private:
size_t n;
std::vector<size_t> father;
std::vector<size_t> depth;
//
size_t _root(size_t now);
size_t _merge(size_t a, size_t b);
public:
DisjointSet();
DisjointSet(size_t _n);
DisjointSet(DisjointSet const& dsj);
//#==== Support Methods
//#
//#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
//#|=====================================================================
//#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
//#|const |root |(size_t `number`) | size_t | very fast
//#|回傳 `number` 所在的 *集合的編號* (0~N-1)
size_t root (size_t a ) const;
//#|const |size |() | size_t | very fast
//#|回傳 *總集合大小*
size_t size ( ) const;
//#| |reset|(size_t `N`) | void | O(N)
//#| 清空, 並且設定總集合大小為 `N`
void reset(size_t _n );
//#| |merge|(size_t `number1`,\size_t `number2`)| size_t | very fast
//#| 將 `number1` 所在的集合 跟 `number2` 所在的集合 *合併*,
//# 並回傳合併後新的集合的編號
size_t merge(size_t a, size_t b);
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * *very fast* 表示它算的真的超級快, 可以視為常數時間.
//# * 預設值所有 `number` 所在的集合的編號就是 `number` 本身,
//# 即沒有任兩個數在同一個set裡面
//#========================================
//#
//# '''
}
#include "DisjointSet.hpp"
#endif // DisjointSet_H__
|
