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

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

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