题目描述

给定一个二分图，求其最大匹配。

思路

1. 为每个节点找一个匹配的对象，如果能找到则匹配值+1
2. 对于要找匹配对象的当前节点，遍历其所有邻接点：
   (1)临接点无匹配对象，则将邻接点的匹配对象设为当前节点
   (2)临接点有匹配对象，则尝试为其匹配对象找一个新的对象，找不到尝试下一个临界点，否则将邻接点的匹配对象设为当前节点。
3. 使用vis记录节点是否被访问过，防止递归为邻接点匹配对象找新的对象的过程中回到该临界点。
4. 每个节点进行匹配之间先清空vis

C++

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

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

int n1, n2, m;
int vis[N], match[N];

bool find(int u)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(vis[j])continue;
        vis[j] = true;
        if(!match[j] || find(match[j]) )
        {
            match[j] = u;
            return true;
        }
    }
    return false;
}

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

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

    cout << res << endl;
    return 0;
}