Adds greedy matching to improve Kuhn's algorithm.

1 files changed, 10 insertions, 8 deletions

diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index c086abc..be65d78 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -3,13 +3,11 @@ vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts.
 vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1.
 vector<bool> visited;
 
-bool dfs(int i) {
-	if (visited[i]) return false;
-	visited[i] = true;
-	for (vector<int>::iterator vit = adjlist[i].begin(); vit != adjlist[i].end(); vit++) {
-		if (pairs[*vit] < 0 || dfs(pairs[*vit])) {
-			pairs[*vit] = i; pairs[i] = *vit; return true;
-		}
+bool dfs(int v) {
+	if (visited[v]) return false;
+	visited[v] = true;
+	for (auto w : adjlist[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
+		pairs[w] = v; pairs[v] = w; return true;
 	}
 	return false;
 }
@@ -18,7 +16,11 @@ bool dfs(int i) {
 int kuhn(int n, int m) {
 	pairs.assign(n + m, -1);
 	int ans = 0;
-	for (int i = 0; i < n; i++) {
+	// 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) {
 		visited.assign(n + m, false);
 		ans += dfs(i);
 	}