1 files changed, 47 insertions, 0 deletions
diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp
new file mode 100644
index 0000000..c1f5d1c
--- /dev/null
+++ b/content/graph/hopcroftKarp.cpp
@@ -0,0 +1,47 @@
+vector<vector<int>> adj;
+// pairs ist der gematchte Knoten oder -1
+vector<int> pairs, dist, ptr;
+
+bool bfs(int l) {
+	queue<int> q;
+	for(int v = 0; v < l; v++) {
+		if (pairs[v] < 0) {dist[v] = 0; q.push(v);}
+		else dist[v] = -1;
+	}
+	bool exist = false;
+	while(!q.empty()) {
+		int v = q.front(); q.pop();
+		for (int u : adj[v]) {
+			if (pairs[u] < 0) {exist = true; continue;}
+			if (dist[pairs[u]] < 0) {
+				dist[pairs[u]] = dist[v] + 1;
+				q.push(pairs[u]);
+	}}}
+	return exist;
+}
+
+bool dfs(int v) {
+	for (; ptr[v] < sz(adj[v]); ptr[v]++) {
+		int u = adj[v][ptr[v]];
+		if (pairs[u] < 0 ||
+		   (dist[pairs[u]] > dist[v] && dfs(pairs[u]))) {
+			pairs[u] = v; pairs[v] = u;
+			return true;
+	}}
+	return false;
+}
+
+int hopcroft_karp(int l) { // l = #Knoten links
+	int ans = 0;
+	pairs.assign(sz(adj), -1);
+	dist.resize(l);
+	// Greedy Matching, optionale Beschleunigung.
+	for (int v = 0; v < l; v++) for (int u : adj[v])
+		if (pairs[u] < 0) {pairs[u] = v; pairs[v] = u; ans++; break;}
+	while(bfs(l)) {
+		ptr.assign(l, 0);
+		for(int v = 0; v < l; v++) {
+			if (pairs[v] < 0) ans += dfs(v);
+	}}
+	return ans;
+}