diff options
Diffstat (limited to 'graph/maxCarBiMatch.cpp')
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index fb9cb3d..c086abc 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,5 +1,6 @@ -vector< vector<int> > adjlist; //seems to work directed, from left to right -vector<int> pairs; //for every node, stores the matching node on the other side or -1 +// Laufzeit: O(n*(|V|+|E|)) +vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts. +vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1. vector<bool> visited; bool dfs(int i) { @@ -13,12 +14,13 @@ bool dfs(int i) { return false; } -int kuhn(int n, int m) { // n = nodes on left side (numbered 0..n-1), m = nodes on the right side +// n = #Knoten links (0..n-1), m = #Knoten rechts +int kuhn(int n, int m) { pairs.assign(n + m, -1); int ans = 0; for (int i = 0; i < n; i++) { visited.assign(n + m, false); ans += dfs(i); } - return ans; //size of the MCBM + return ans; // Größe des Matchings. } |