From 110ddc3a722b3f6c1d3c1ebdaeddb0d8881ba96a Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 22:49:13 +0200 Subject: Maximum cardinality bipartite matching improved. --- graph/maxCarBiMatch.cpp | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'graph') diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index be65d78..a6a242f 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,6 +1,6 @@ -// Laufzeit: O(n*(|V|+|E|)) -vector< vector > adjlist; // Gerichtete Kanten, von links nach rechts. -vector pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1. +// Laufzeit: O(n*min(ans^2, |E|)) +vector< vector > adjlist; // Von links nach rechts. +vector pairs; // Der gematchte Knoten oder -1. vector visited; bool dfs(int v) { @@ -12,16 +12,14 @@ bool dfs(int v) { return false; } -// n = #Knoten links (0..n-1), m = #Knoten rechts -int kuhn(int n, int m) { - pairs.assign(n + m, -1); +int kuhn(int n) { // n = #Knoten links. + pairs.assign(adjlist.size(), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. - for (int i = 0; i < n; i++) for (auto w : adjlist[i]) if (pairs[w] == -1) { - pairs[i] = w; pairs[w] = i; ans++; break; - } + for (int i = 0; i < n; i++) for (auto w : adjlist[i]) + if (pairs[w] == -1) pairs[i] = w; pairs[w] = i; ans++; break; } for (int i = 0; i < n; i++) if (pairs[i] == -1) { - visited.assign(n + m, false); + visited.assign(n, false); ans += dfs(i); } return ans; // Größe des Matchings. -- cgit v1.2.3