1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#ifndef dsa_DisjointSet_H__
#define dsa_DisjointSet_H__
#include <cstdlib>
#include <vector>
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 // dsa_DisjointSet_H__
|
