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/maxCarBiMatch.cpp | |
| parent | f209418070050d4310a19191e3cd771760e5b521 (diff) | |
consistency
Diffstat (limited to 'graph/maxCarBiMatch.cpp')
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 8 |
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); |
