From e95f59debd69ee7d45d5c966ce466d23264e1c3c Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Sat, 16 Nov 2024 18:12:15 +0100
Subject: rename maxCarBiMatch.cpp to kuhn.cpp

---
 content/graph/graph.tex         |  2 +-
 content/graph/kuhn.cpp          | 25 +++++++++++++++++++++++++
 content/graph/maxCarBiMatch.cpp | 25 -------------------------
 3 files changed, 26 insertions(+), 26 deletions(-)
 create mode 100644 content/graph/kuhn.cpp
 delete mode 100644 content/graph/maxCarBiMatch.cpp

(limited to 'content')

diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index b38e96e..6e8e20b 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -188,7 +188,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\begin{itemize}
 		\item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen
 	\end{itemize}
-	\sourcecode{graph/maxCarBiMatch.cpp}
+	\sourcecode{graph/kuhn.cpp}
 	\begin{methods}
 		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
 	\end{methods}
diff --git a/content/graph/kuhn.cpp b/content/graph/kuhn.cpp
new file mode 100644
index 0000000..e928387
--- /dev/null
+++ b/content/graph/kuhn.cpp
@@ -0,0 +1,25 @@
+vector<vector<int>> adj;
+vector<int> pairs; // Der gematchte Knoten oder -1.
+vector<bool> visited;
+
+bool dfs(int v) {
+	if (visited[v]) return false;
+	visited[v] = true;
+	for (int u : adj[v]) if (pairs[u] < 0 || dfs(pairs[u])) {
+		pairs[u] = v; pairs[v] = u; return true;
+	}
+	return false;
+}
+
+int kuhn(int l) { // l = #Knoten links.
+	pairs.assign(sz(adj), -1);
+	int ans = 0;
+	// 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;}
+	for (int v = 0; v < l; v++) if (pairs[v] < 0) {
+		visited.assign(l, false);
+		ans += dfs(v);
+	}
+	return ans; // Größe des Matchings.
+}
diff --git a/content/graph/maxCarBiMatch.cpp b/content/graph/maxCarBiMatch.cpp
deleted file mode 100644
index e928387..0000000
--- a/content/graph/maxCarBiMatch.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-vector<vector<int>> adj;
-vector<int> pairs; // Der gematchte Knoten oder -1.
-vector<bool> visited;
-
-bool dfs(int v) {
-	if (visited[v]) return false;
-	visited[v] = true;
-	for (int u : adj[v]) if (pairs[u] < 0 || dfs(pairs[u])) {
-		pairs[u] = v; pairs[v] = u; return true;
-	}
-	return false;
-}
-
-int kuhn(int l) { // l = #Knoten links.
-	pairs.assign(sz(adj), -1);
-	int ans = 0;
-	// 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;}
-	for (int v = 0; v < l; v++) if (pairs[v] < 0) {
-		visited.assign(l, false);
-		ans += dfs(v);
-	}
-	return ans; // Größe des Matchings.
-}
-- 
cgit v1.2.3