diff options
Diffstat (limited to 'graph/maxCarBiMatch.cpp')
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 8 |
1 files changed, 3 insertions, 5 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index 24aebef..0a38d84 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,5 +1,3 @@ -// Laufzeit: O(n*min(ans^2, |E|)) -// Kanten von links nach rechts. Die ersten n Knoten sind links, die anderen rechts. vector<vector<int>> adjlist; vector<int> pairs; // Der gematchte Knoten oder -1. vector<bool> visited; @@ -14,12 +12,12 @@ bool dfs(int v) { } int kuhn(int n) { // n = #Knoten links. - pairs.assign(adjlist.size(), -1); + pairs.assign(sz(adjlist), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int i = 0; i < n; i++) for (auto w : adjlist[i]) - if (pairs[w] == -1) { pairs[i] = w; pairs[w] = i; ans++; break; } - for (int i = 0; i < n; i++) if (pairs[i] == -1) { + 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); ans += dfs(i); } |