二分图匹配

const int INF = 1e9;
vector<int> g[MAXN];   // g[u]：左点 u 能匹配的右点列表（邻接表）
int matchL[MAXN];      // matchL[u]：左点 u 当前匹配到的右点，0 表示空闲
int matchR[MAXN];      // matchR[v]：右点 v 当前匹配到的左点，0 表示空闲
int distL[MAXN];       // distL[u]：BFS 分层中左点 u 的层数，INF 表示未访问

bool bfs() {
  queue<int> q;
  for (int u = 1; u <= nL; ++u) {
    if (matchL[u] == 0) distL[u] = 0, q.push(u);   // 所有自由左点作为第 0 层
    else distL[u] = INF;
  }
  distL[0] = INF; // 0 号是虚拟空闲右点：所有空闲右点都指向它
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u])
      // 右点 v 空闲（matchR[v] == 0）时走到虚拟点；否则沿匹配边走回左点 matchR[v]
      if (distL[matchR[v]] == INF) {
        distL[matchR[v]] = distL[u] + 1;
        q.push(matchR[v]);
      }
  }
  return distL[0] != INF; // 能到达虚拟空闲右点 -> 存在增广路
}

bool dfs(int u) {
  if (u == 0) return true; // 走到虚拟空闲右点，增广路终点已找到
  for (int v : g[u])
    if (distL[matchR[v]] == distL[u] + 1 && dfs(matchR[v])) {
      matchR[v] = u; // 右点 v 改配左点 u
      matchL[u] = v; // 左点 u 匹配右点 v
      return true;
    }
  distL[u] = INF; // 剪枝：u 已无路可走
  return false;
}

int hopcroftKarp() {
  int ans = 0;
  while (bfs())
    for (int u = 1; u <= nL; ++u)
      if (matchL[u] == 0 && dfs(u)) ++ans; // 只从自由左点出发增广
  return ans;
}