matbensch

CP Kuhn's

Mar 5th, 2022
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.60 KB | None | 0 0
  1. int n, k;
  2. vector<vector<int>> g;
  3. vector<int> mt;
  4. vector<bool> used;
  5.  
  6. bool try_kuhn(int v) {
  7.     if (used[v])
  8.         return false;
  9.     used[v] = true;
  10.     for (int to : g[v]) {
  11.         if (mt[to] == -1 || try_kuhn(mt[to])) {
  12.             mt[to] = v;
  13.             return true;
  14.         }
  15.     }
  16.     return false;
  17. }
  18.  
  19. int main() {
  20.     //... reading the graph ...
  21.  
  22.     mt.assign(k, -1);
  23.     for (int v = 0; v < n; ++v) {
  24.         used.assign(n, false);
  25.         try_kuhn(v);
  26.     }
  27.  
  28.     for (int i = 0; i < k; ++i)
  29.         if (mt[i] != -1)
  30.             printf("%d %d\n", mt[i] + 1, i + 1);
  31. }
  32.  
Advertisement
Add Comment
Please, Sign In to add comment