定义从未匹配点出发，依次经过匹配边、非匹配边、匹配边......所形成的路径叫交替路，从一个未匹配点出发，走交替路，如果途径另一个未匹配点（起始点不包括），则这条交替路称为增广路。

通过不停地找增广路来增加匹配中的匹配边和匹配点，当找不到增广路时，可以获得二分图的最大匹配。

算法时间复杂度$O(|V|*|E|)$。

//luogu P3386
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;

int n, m, e;
bool G[N][N];
bool vis[N];
int match_y[N];
int ans;

bool match(int x) {
    for ( int y = 1; y <= m; ++y ) {
        if ( !vis[y] && G[x][y] ) {
            vis[y] = true;
            if ( match_y[y] == -1 || match(match_y[y]) ) {
                match_y[y] = x;

                return true;
            }
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m >> e;

    int u, v;
    for ( int i = 1; i <= e; ++i ) {
        cin >> u >> v;

        if ( u <= n && v <= m )
            G[u][v] = true;
    }

    memset(match_y, -1, sizeof match_y);
    for ( int i = 1; i <= n; ++i ) {
        ans += match(i);
        memset(vis, 0, sizeof vis);
    }

    cout << ans << endl;

    return 0;
}

拓展资料：

• https://www.renfei.org/blog/bipartite-matching.html