题目描述

给定一个二分图，其中左半部包含 n1 个点（编号1~ n1 ），右半部包含 n2 个点（编号1~ n2 ），二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式

第一行包含三个整数 n1 、 n2 和 m 。

接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

1≤n1,n2≤500 ,
1≤u≤n1 ,
1≤v≤n2 ,
1≤m≤105

样例

输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2

C++代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define N 501

int head[N],n1,n2,m,cnt;
int match[N];
bool vis[N];

struct edge
{
    int to,nex;
}e[N << 1];

void add(int from,int to)
{
    e[++cnt] = (edge){to,head[from]};
    head[from] = cnt;
}

bool find(int x)
{
    for (int i = head[x]; i; i = e[i].nex)
    {
        int too = e[i].to;
        if (!vis[too])  
        {
            vis[too] = true;
            if (!match[too] || find(match[too])) // 如果对面没有配偶，就当她的配偶；如果有，就去问问她的配偶可以不可以换个人(.......)
            {
                match[too] = true;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    for (int i = 1; i <= m; i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }

    int ans = 0;

    for (int i = 1; i <= n1; i++)
    {
        memset(vis , false , sizeof vis);
        if (find(i)) ans++;
    }
    cout << ans;
    return 0;
}