summaryrefslogtreecommitdiff
path: root/graph/blossom.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2023-08-29 00:09:28 +0200
committermzuenni <michi.zuendorf@gmail.com>2023-08-29 00:09:28 +0200
commit4905811a7c635f28827984a999aedacd910f4dc3 (patch)
treed21228d541bb14dc2dc29ffdff2331dfb5ba6b1e /graph/blossom.cpp
parentf209418070050d4310a19191e3cd771760e5b521 (diff)
consistency
Diffstat (limited to 'graph/blossom.cpp')
-rw-r--r--graph/blossom.cpp20
1 files changed, 10 insertions, 10 deletions
diff --git a/graph/blossom.cpp b/graph/blossom.cpp
index 13a3246..dd9d000 100644
--- a/graph/blossom.cpp
+++ b/graph/blossom.cpp
@@ -1,11 +1,11 @@
struct GM {
- vector<vector<int>> adjlist;
+ vector<vector<int>> adj;
// pairs ist der gematchte knoten oder n
vector<int> pairs, first, que;
vector<pair<int, int>> label;
int head, tail;
- GM(int n) : adjlist(n), pairs(n + 1, n), first(n + 1, n),
+ GM(int n) : adj(n), pairs(n + 1, n), first(n + 1, n),
que(n), label(n + 1, {-1, -1}) {}
void rematch(int v, int w) {
@@ -32,7 +32,7 @@ struct GM {
auto h = label[r] = label[s] = {~x, y};
int join;
while (true) {
- if (s != sz(adjlist)) swap(r, s);
+ if (s != sz(adj)) swap(r, s);
r = findFirst(label[pairs[r]].first);
if (label[r] == h) {
join = r;
@@ -48,13 +48,13 @@ struct GM {
}}}
bool augment(int u) {
- label[u] = {sz(adjlist), -1};
- first[u] = sz(adjlist);
+ label[u] = {sz(adj), -1};
+ first[u] = sz(adj);
head = tail = 0;
for (que[tail++] = u; head < tail;) {
int x = que[head++];
- for (int y : adjlist[x]) {
- if (pairs[y] == sz(adjlist) && y != u) {
+ for (int y : adj[x]) {
+ if (pairs[y] == sz(adj) && y != u) {
pairs[y] = x;
rematch(x, y);
return true;
@@ -70,12 +70,12 @@ struct GM {
int match() {
int matching = head = tail = 0;
- for (int u = 0; u < sz(adjlist); u++) {
- if (pairs[u] < sz(adjlist) || !augment(u)) continue;
+ for (int u = 0; u < sz(adj); u++) {
+ if (pairs[u] < sz(adj) || !augment(u)) continue;
matching++;
for (int i = 0; i < tail; i++)
label[que[i]] = label[pairs[que[i]]] = {-1, -1};
- label[sz(adjlist)] = {-1, -1};
+ label[sz(adj)] = {-1, -1};
}
return matching;
}