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
|
#include "union_find.hpp"
#include "utils.hpp"
#include <algorithm>
#include <cassert>
namespace terraces {
union_find::union_find(index_t n, utils::stack_allocator<index_t> a) : m_parent(n, n, a) {
#ifndef NDEBUG
m_compressed = true;
#endif // NDEBUG
}
index_t union_find::find(index_t x) {
assert(x < m_parent.size());
index_t root = x;
while (!is_representative(root)) {
root = m_parent[root];
}
while (x != root) {
x = utils::exchange(m_parent[x], root);
}
assert(is_representative(root) && root < m_parent.size());
return root;
}
void union_find::compress() {
for (index_t i = 0; i < m_parent.size(); ++i) {
find(i);
}
#ifndef NDEBUG
m_compressed = true;
#endif // NDEBUG
}
void union_find::merge(index_t x, index_t y) {
#ifndef NDEBUG
m_compressed = false;
#endif // NDEBUG
index_t i = find(x);
index_t j = find(y);
if (i == j) {
return;
}
if (m_parent[i] < m_parent[j]) {
// link the smaller group to the larger one
m_parent[i] = j;
} else if (m_parent[i] > m_parent[j]) {
// link the smaller group to the larger one
m_parent[j] = i;
} else {
// equal rank: link arbitrarily and increase rank
m_parent[j] = i;
++m_parent[i];
}
}
union_find union_find::make_bipartition(const std::vector<bool>& split,
utils::stack_allocator<index_t> alloc) {
union_find result(split.size(), alloc);
std::array<index_t, 2> fst{{none, none}};
for (index_t i = 0; i < split.size(); ++i) {
auto& repr = fst[split[i]];
repr = repr == none ? i : repr;
result.merge(repr, i);
}
result.compress();
return result;
}
} // namespace terraces
|
