From 8f0cbc24424420b9ab0149429272c18e0a66c10a Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc56.atis-stud.uni-karlsruhe.de>
Date: Tue, 25 Nov 2014 12:00:30 +0100
Subject: bipartites matching

---
 graph/maxCarBiMatch.cpp | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 graph/maxCarBiMatch.cpp

(limited to 'graph/maxCarBiMatch.cpp')

diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
new file mode 100644
index 0000000..d46ce9d
--- /dev/null
+++ b/graph/maxCarBiMatch.cpp
@@ -0,0 +1,24 @@
+vector< vector<int> > adjlist;
+vector<int> pairs; //for every node, stores the matching node on the other side or -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;
+		}
+	}
+	return false;
+}
+
+int kuhn(int n, int m) { // n = nodes on left side (numbered 0..n-1), m = nodes on the right side
+	pairs.assign(n + m, -1);
+	int ans = 0;
+	for (int i = 0; i < n; i++) {
+		visited.assign(n + m, false);
+		ans += dfs(i);
+	}
+	return ans; //size of the MCBM
+}
\ No newline at end of file
-- 
cgit v1.2.3