From e95f59debd69ee7d45d5c966ce466d23264e1c3c Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 18:12:15 +0100 Subject: rename maxCarBiMatch.cpp to kuhn.cpp --- content/graph/maxCarBiMatch.cpp | 25 ------------------------- 1 file changed, 25 deletions(-) delete mode 100644 content/graph/maxCarBiMatch.cpp (limited to 'content/graph/maxCarBiMatch.cpp') 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> adj; -vector pairs; // Der gematchte Knoten oder -1. -vector 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