Kuhn's algorithm

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
645 B
5
Indexable
Never
class Kuhn
{
  vector<int> used;
  vector<int> r;
  int n;
  Kuhn(int n){
    this->n = n;
    used.resize(n + 1);
    r.resize(n + 1);
  } 

  bool dfs(int v)
  {
    if (used[v])
      return false;
    used[v] = true;
    // Change the graph name to your own
    for(auto to:g[v])
      if (r[to] == -1 || dfs(r[to]))
      {
        r[to] = v;
        return true;
      }
    return false;
  }

  int kuhn()
  {
    fill(begin(r), end(r),-1);
    int ans = 0;
    for (int v = 0; v < n; v++)
    {
      fill(begin(used), end(used), false);
      if (dfs(v))
        ans++;
    }
    return ans;
  }
};