Maximum cardinality bipartite matching improved.

1 files changed, 8 insertions, 10 deletions

diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index be65d78..a6a242f 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -1,6 +1,6 @@
-// Laufzeit: O(n*(|V|+|E|))
-vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts.
-vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1.
+// Laufzeit: O(n*min(ans^2, |E|))
+vector< vector<int> > adjlist; // Von links nach rechts.
+vector<int> pairs; // Der gematchte Knoten oder -1.
 vector<bool> visited;
 
 bool dfs(int v) {
@@ -12,16 +12,14 @@ bool dfs(int v) {
 	return false;
 }
 
-// n = #Knoten links (0..n-1), m = #Knoten rechts
-int kuhn(int n, int m) {
-	pairs.assign(n + m, -1);
+int kuhn(int n) { // n = #Knoten links.
+	pairs.assign(adjlist.size(), -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++) 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) {
-		visited.assign(n + m, false);
+		visited.assign(n, false);
 		ans += dfs(i);
 	}
 	return ans; // Größe des Matchings.