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/graph.tex         |   3 +++
 graph/maxCarBiMatch.cpp |  24 ++++++++++++++++++++++++
 tcr.pdf                 | Bin 172283 -> 174553 bytes
 3 files changed, 27 insertions(+)
 create mode 100644 graph/maxCarBiMatch.cpp

diff --git a/graph/graph.tex b/graph/graph.tex
index 79404d4..8d525f6 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -66,3 +66,6 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
 	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten.
 \end{enumerate}
 
+\subsubsection{Maximal Cardinatlity Bipartite Mathcing}
+\lstinputlisting{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
diff --git a/tcr.pdf b/tcr.pdf
index 3c7a487..a680c56 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3