updated tcr

1 files changed, 34 insertions, 37 deletions

diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp
index 629ebf7..132b249 100644
--- a/graph/hopcroftKarp.cpp
+++ b/graph/hopcroftKarp.cpp
@@ -1,46 +1,43 @@
-// Laufzeit: O(sqrt(|V|)*|E|)
-// Kanten von links nach rechts.
-// 0: dummy Knoten, 1..n: linke Knoten, n+1..n+m: rechte Knoten
 vector<vector<int>> adjlist;
-vector<int> match, dist;
+// pairs ist der gematchte Knoten oder -1
+vector<int> pairs, dist;
 
 bool bfs(int n) {
-  queue<int> q;
-  dist[0] = INF;
-  for(int i = 1; i <= n; i++) {
-    if(match[i] == 0) { dist[i] = 0; q.push(i); }
-    else dist[i] = INF;
-  }
-  while(!q.empty()) {
-    int u = q.front(); q.pop();
-    if(dist[u] < dist[0]) for (int v : adjlist[u])
-      if(dist[match[v]] == INF) {
-        dist[match[v]] = dist[u] + 1;
-        q.push(match[v]);
-      }
-  }
-  return dist[0] != INF;
+	queue<int> q;
+	for(int i = 0; i < n; i++) {
+		if (pairs[i] < 0) {dist[i] = 0; q.push(i);}
+		else dist[i] = -1;
+	}
+	while(!q.empty()) {
+		int u = q.front(); q.pop();
+		for (int v : adjlist[u]) {
+			if (pairs[v] < 0) return true;
+			if (dist[pairs[v]] < 0) {
+				dist[pairs[v]] = dist[u] + 1;
+				q.push(pairs[v]);
+	}}}
+	return false;
 }
 
 bool dfs(int u) {
-  if(u != 0) {
-    for (int v : adjlist[u])
-      if(dist[match[v]] == dist[u] + 1)
-        if(dfs(match[v])) { match[v] = u; match[u] = v; return true; }
-    dist[u] = INF;
-    return false;
-  }
-  return true;
+	for (int v : adjlist[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 ans = 0;
-  match.assign(adjlist.size(), 0);
-  dist.resize(adjlist.size());
-  // Greedy Matching, optionale Beschleunigung.
-  for (int i = 1; i <= n; i++) for (int w : adjlist[i])
-    if (match[w] == 0) { match[i] = w; match[w] = i; ans++; break; }
-  while(bfs(n)) for(int i = 1; i <= n; i++)
-    if(match[i] == 0 && dfs(i)) ans++;
-  return ans;
-}
+	int ans = 0;
+	pairs.assign(sz(adjlist), -1);
+	dist.resize(n);
+	// Greedy Matching, optionale Beschleunigung.
+	for (int i = 0; i < n; i++) for (int w : adjlist[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);
+	return ans;
+}
\ No newline at end of file