python/TangDou/AcWing/BipartiteGraph/861.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int M = 100010;

int n1, n2;
int m;

int match[N];
int st[N];
int res;

int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!st[v]) {
            st[v] = 1;
            if (match[v] == 0 || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n1; i++) {
        memset(st, 0, sizeof st);
        if (dfs(i)) res++;
    }

    printf("%d\n", res);
    return 0;
}