HopcroftKarp

struct HopcroftKarp {
  int n;
  int m;
  int match_cnt;
  std::vector<int> lft;
  std::vector<int> rgt;
  std::vector<std::vector<int>> adj;

  HopcroftKarp(int n, int m) : n(n), m(m), match_cnt(0), lft(n, -1), rgt(m, -1), adj(n) {
    void(0);
  }

  void addEdge(int u, int v) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < m);
    adj[u].push_back(v);
  }

  int work() {
    int total_flow = 0;
    while (true) {
      std::vector<int> lvl(n, -1);
      std::vector<int> que;
      for (int i = 0; i < n; ++i) {
        if (lft[i] == -1) {
          lvl[i] = 0;
          que.push_back(i);
        }
      }
      for (int b = 0; b < int(que.size()); ++b) {
        for (int x : adj[que[b]]) {
          if (rgt[x] != -1 && lvl[rgt[x]] == -1) {
            lvl[rgt[x]] = lvl[que[b]] + 1;
            que.push_back(rgt[x]);
          }
        }
      }
      int flow = 0;
      auto dfs = [&](auto&& dfs, int u) -> bool {
        for (int x : adj[u]) {
          if (rgt[x] == -1 || (lvl[rgt[x]] == lvl[u] + 1 && dfs(dfs, rgt[x]))) {
            lft[u] = x;
            rgt[x] = u;
            return true;
          }
        }
        return false;
      };
      for (int i = 0; i < n; ++i) {
        if (lft[i] == -1 && dfs(dfs, i)) {
          flow += 1;
        }
      }
      if (flow == 0) {
        break;
      }
      total_flow += flow;
    }
    match_cnt += total_flow;
    return total_flow;
  }
};