1 files changed, 24 insertions, 0 deletions
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