diff options
| author | mzuenni <michi.zuendorf@gmail.com> | 2023-08-29 00:09:28 +0200 |
|---|---|---|
| committer | mzuenni <michi.zuendorf@gmail.com> | 2023-08-29 00:09:28 +0200 |
| commit | 4905811a7c635f28827984a999aedacd910f4dc3 (patch) | |
| tree | d21228d541bb14dc2dc29ffdff2331dfb5ba6b1e /graph/blossom.cpp | |
| parent | f209418070050d4310a19191e3cd771760e5b521 (diff) | |
consistency
Diffstat (limited to 'graph/blossom.cpp')
| -rw-r--r-- | graph/blossom.cpp | 20 |
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; } |
