blob: 9be9c355648003b66cf31e773939583b65348d6f (
plain) (
blame)
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#ifndef dsa_DisjointSet_H__
#define dsa_DisjointSet_H__
#include <vector>
#include <cstdlib>
#include <cstdio>
namespace meow {
/*!
* @brief 用來維護一堆互斥集的資訊
*
* DisjointSet 是個 \b 輕量級Data \b Dtructure, 用來維護一堆互斥集的資訊. \n
* 相關資料可參考
* <a href="http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html">
* 演算法筆記
* </a>
*
* @note
* - 時間複雜度 \b 非常快 表示它真的算的超級快, 可以視為常數時間
* - 預設值所有 \a number 所在的集合的編號就是 \a number 本身,
* 即沒有任兩個數在同一個set裡面
*
* @author cat_leopard
*/
class DisjointSet {
private:
size_t n_;
std::vector<size_t> father_;
std::vector<size_t> depth_;
//
size_t root_(size_t now) {
if (father_[now] == now) return now;
return (father_[now] = root_(father_[now]));
}
size_t merge_(size_t a, size_t b) {
a = root_(a);
b = root_(b);
if (a == b) return a;
if (depth_[a] > depth_[b]) {
father_[b] = a;
return a;
}
else {
father_[a] = b;
if (depth_[a] == depth_[b]) depth_[b]++;
return b;
}
}
public:
/*!
*@brief constructor
*/
DisjointSet(): n_(0) {
}
/*!
*@brief constructor
*
*@param [in] n elements數
*/
DisjointSet(size_t n) {
reset(n);
}
/*!
*@brief constructor
*
*將另一個 \c DisjointSet 原封不動的複製過來
*
*@param [in] dsj 另一個 \c DisjointSet
*/
DisjointSet(DisjointSet const& dsj):
n_(dsj.n_), father_(dsj.father_), depth_(dsj.depth_) {
}
/*!
*@brief 回傳指定的number所在的 \b 集合的編號
*
*時間複雜度 \b 超級快
*
*@param [in] a 指定的number
*@return 集合的編號
*/
size_t root(size_t a) const {
return ((DisjointSet*)this)->root_(a);
}
/*!
*@brief 回傳總element數
*
*@return 總element數
*/
size_t size() const {
return n_;
}
/*!
*@brief 重設
*
*清空, 並且設定總集合大小為 \a n
*
*@param [in] n 重新設定的集合大小 \a n
*@return 無
*/
void reset(size_t n) {
n_ = n;
father_.resize(n);
depth_ .resize(n);
for (size_t i = 0; i < n; i++) {
father_[i] = i;
depth_ [i] = 1;
}
}
/*!
* @brief 合併
*
* 將 \a number1 所在的集合 跟 \b number2 所在的集合 \b 合併,
* 並回傳合併後新的集合的編號. \n
* 時間複雜度\b 非常快
*
* @param [in] a 即上述\a number1
* @param [in] b 即上述\a number2
* @return 新的編號
*/
size_t merge(size_t a, size_t b) {
return merge_(a, b);
}
};
}
#endif // dsa_DisjointSet_H__
|
