summaryrefslogtreecommitdiff
path: root/graph/maxCarBiMatch.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/maxCarBiMatch.cpp
parentf209418070050d4310a19191e3cd771760e5b521 (diff)
consistency
Diffstat (limited to 'graph/maxCarBiMatch.cpp')
-rw-r--r--graph/maxCarBiMatch.cpp8
1 files changed, 4 insertions, 4 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index 0a38d84..588568b 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -1,21 +1,21 @@
-vector<vector<int>> adjlist;
+vector<vector<int>> adj;
vector<int> pairs; // Der gematchte Knoten oder -1.
vector<bool> visited;
bool dfs(int v) {
if (visited[v]) return false;
visited[v] = true;
- for (auto w : adjlist[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
+ for (auto w : adj[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
pairs[w] = v; pairs[v] = w; return true;
}
return false;
}
int kuhn(int n) { // n = #Knoten links.
- pairs.assign(sz(adjlist), -1);
+ pairs.assign(sz(adj), -1);
int ans = 0;
// Greedy Matching. Optionale Beschleunigung.
- for (int i = 0; i < n; i++) for (auto w : adjlist[i])
+ for (int i = 0; i < n; i++) for (auto w : adj[i])
if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;}
for (int i = 0; i < n; i++) if (pairs[i] < 0) {
visited.assign(n, false);