lessons/参考实现/07-二分图/POJ-3041.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<vector<int>> g(n);
    while (k--) { int row, column; cin >> row >> column; g[row - 1].push_back(column - 1); }
    vector<int> match(n, -1), seen(n); int token = 0, answer = 0;
    auto augment = [&](auto &&self, int row) -> bool {
        for (int column : g[row]) if (seen[column] != token) {
            seen[column] = token;
            if (match[column] == -1 || self(self, match[column])) {
                match[column] = row; return true;
            }
        }
        return false;
    };
    for (int row = 0; row < n; ++row) { ++token; answer += augment(augment, row); }
    cout << answer << '\n';
}