From 46c7370481a22b0b6134c0fd560b78f99864a9e1 Mon Sep 17 00:00:00 2001
From: Noobie99 <noob999noob999@gmail.com>
Date: Mon, 10 Jul 2023 18:48:56 +0200
Subject: improved dinic, sped up hopcroft-karp

---
 graph/hopcroftKarp.cpp | 34 +++++++++++++++++++---------------
 1 file changed, 19 insertions(+), 15 deletions(-)

(limited to 'graph/hopcroftKarp.cpp')

diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp
index 09d27bc..61ec469 100644
--- a/graph/hopcroftKarp.cpp
+++ b/graph/hopcroftKarp.cpp
@@ -1,43 +1,47 @@
-vector<vector<int>> adjlist;
+vector<vector<int>> adj;
 // pairs ist der gematchte Knoten oder -1
-vector<int> pairs, dist;
+vector<int> pairs, dist, ptr;
 
-bool bfs(int n) {
+bool bfs(int l) {
 	queue<int> q;
-	for(int i = 0; i < n; i++) {
+	for(int i = 0; i < l; i++) {
 		if (pairs[i] < 0) {dist[i] = 0; q.push(i);}
 		else dist[i] = -1;
 	}
+	bool exist = false;
 	while(!q.empty()) {
 		int u = q.front(); q.pop();
-		for (int v : adjlist[u]) {
-			if (pairs[v] < 0) return true;
+		for (int v : adj[u]) {
+			if (pairs[v] < 0) {exist = true; continue;}
 			if (dist[pairs[v]] < 0) {
 				dist[pairs[v]] = dist[u] + 1;
 				q.push(pairs[v]);
 	}}}
-	return false;
+	return exist;
 }
 
 bool dfs(int u) {
-	for (int v : adjlist[u]) {
+	for (; ptr[u] < sz(adj[u]); ptr[u]++) {
+		int v = adj[u][ptr[u]];
 		if (pairs[v] < 0 ||
 		   (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) {
 			pairs[v] = u; pairs[u] = v;
 			return true;
 	}}
-	dist[u] = -1;
 	return false;
 }
 
-int hopcroft_karp(int n) { // n = #Knoten links
+int hopcroft_karp(int l) { // l = #Knoten links
 	int ans = 0;
-	pairs.assign(sz(adjlist), -1);
-	dist.resize(n);
+	pairs.assign(sz(adj), -1);
+	dist.resize(l);
 	// Greedy Matching, optionale Beschleunigung.
-	for (int i = 0; i < n; i++) for (int w : adjlist[i])
+	for (int i = 0; i < l; i++) for (int w : adj[i])
 		if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;}
-	while(bfs(n)) for(int i = 0; i < n; i++)
-		if (pairs[i] < 0) ans += dfs(i);
+	while(bfs(l)) {
+		ptr.assign(l, 0);
+		for(int i = 0; i < l; i++) {
+			if (pairs[i] < 0) ans += dfs(i);
+	}}
 	return ans;
 }
-- 
cgit v1.2.3