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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
#ifndef DISAJOINT_TREE_H_
#define DISAJOINT_TREE_H_
#include <vector>
namespace qflow {
class DisajointTree {
public:
DisajointTree() {}
DisajointTree(int n) {
parent.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; ++i) parent[i] = i;
}
int Parent(int x) {
if (x == parent[x]) return x;
int y = Parent(parent[x]);
parent[x] = y;
return y;
}
int Index(int x) { return indices[x]; }
int IndexToParent(int x) {return indices_to_parent[x]; };
void MergeFromTo(int x, int y) {
int px = Parent(x);
int py = Parent(y);
if (px == py) return;
rank[py] += rank[px];
parent[px] = py;
}
void Merge(int x, int y) {
int px = Parent(x);
int py = Parent(y);
if (px == py) return;
if (rank[px] < rank[py]) {
rank[py] += rank[px];
parent[px] = py;
} else {
rank[px] += rank[py];
parent[py] = px;
}
}
// renumber the root so that it is consecutive.
void BuildCompactParent() {
std::vector<int> compact_parent;
compact_parent.resize(parent.size());
compact_num = 0;
for (int i = 0; i < parent.size(); ++i) {
if (parent[i] == i) {
compact_parent[i] = compact_num++;
indices_to_parent.push_back(i);
}
}
indices.resize(parent.size());
for (int i = 0; i < parent.size(); ++i) {
indices[i] = compact_parent[Parent(i)];
}
}
int CompactNum() { return compact_num; }
int compact_num;
std::vector<int> parent;
std::vector<int> indices, indices_to_parent;
std::vector<int> rank;
};
class DisajointOrientTree {
public:
DisajointOrientTree() {}
DisajointOrientTree(int n) {
parent.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; ++i) parent[i] = std::make_pair(i, 0);
}
int Parent(int j) {
if (j == parent[j].first) return j;
int k = Parent(parent[j].first);
parent[j].second = (parent[j].second + parent[parent[j].first].second) % 4;
parent[j].first = k;
return k;
}
int Orient(int j) {
if (j == parent[j].first) return parent[j].second;
return (parent[j].second + Orient(parent[j].first)) % 4;
}
int Index(int x) { return indices[x]; }
void MergeFromTo(int v0, int v1, int orient0, int orient1) {
int p0 = Parent(v0);
int p1 = Parent(v1);
if (p0 == p1) return;
int orientp0 = Orient(v0);
int orientp1 = Orient(v1);
if (p0 == p1) {
return;
}
rank[p1] += rank[p0];
parent[p0].first = p1;
parent[p0].second = (orient0 - orient1 + orientp1 - orientp0 + 8) % 4;
}
void Merge(int v0, int v1, int orient0, int orient1) {
int p0 = Parent(v0);
int p1 = Parent(v1);
if (p0 == p1) {
return;
}
int orientp0 = Orient(v0);
int orientp1 = Orient(v1);
if (p0 == p1) {
return;
}
if (rank[p1] < rank[p0]) {
rank[p0] += rank[p1];
parent[p1].first = p0;
parent[p1].second = (orient1 - orient0 + orientp0 - orientp1 + 8) % 4;
} else {
rank[p1] += rank[p0];
parent[p0].first = p1;
parent[p0].second = (orient0 - orient1 + orientp1 - orientp0 + 8) % 4;
}
}
void BuildCompactParent() {
std::vector<int> compact_parent;
compact_parent.resize(parent.size());
compact_num = 0;
for (int i = 0; i < parent.size(); ++i) {
if (parent[i].first == i) {
compact_parent[i] = compact_num++;
}
}
indices.resize(parent.size());
for (int i = 0; i < parent.size(); ++i) {
indices[i] = compact_parent[Parent(i)];
}
}
int CompactNum() { return compact_num; }
int compact_num;
std::vector<std::pair<int, int>> parent;
std::vector<int> indices;
std::vector<int> rank;
};
} // namespace qflow
#endif
|
