梳理整个算法：
1. 依次枚举每一个点i；
2. 若点i尚未匹配，则以此点为起点查询一次交错路径。
最后即可得到最大匹配数。
在这个基础上仍然有两个可以优化的地方：
1.对于点的枚举：当我们枚举了所有A中的点后，无需再枚举B中的点，就已经得到了最大匹配。
2.
在查询交错路径的过程中，有可能出现Ai与Bj直接相连，其中Bj为已经匹配的点，且Bj之后找不到交错路径。之后又通过Ai查找到了一条交错路径
{Ai,Bx,Ay,…,Az,Bj}延伸到Bj。由于之前已经计算过Bj没有交错路径，若此时再计算一次就有了额外的冗余。所以我们需要枚举每个Ai时
记录B集合中的点是否已经查询过，起点不同时需要清空记录。
伪代码：
Function FindPath(u)
For v∈u的相邻节点
标记v已经查询过
If v未匹配 or FindPath(v的匹配的点) Then
更改u的匹配为v
Return Ture
End If
End For
Return False For i ∈ V
清空标记
FindPath(i)
End If
输入
第1行：2个正整数，N,M(N表示点数 2≤N≤1,000，M表示边数1≤M≤5,000)
第2..M+1行：每行两个整数u,v，表示一条无向边(u,v)
输出
第1行：1个整数，表示最大匹配数
- 样例输入
5 4
3 2
1 3
5 4
1 5- 样例输出
2 代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define N 1001 using namespace std;
int n, m;
int map[N][N];
int link[N];
bool vis[N]; int dfs(int dd)
{
for(int i=; i<=n; i++)
{
if(vis[i]==false && map[dd][i]== )
{
vis[i]=true;
if(link[i]==- || dfs(link[i]) )
{
link[i]=dd;
return ;
}
}
}
return ;
} int main()
{
scanf("%d %d", &n, &m);
int i, j;
int u, v;
memset(map, , sizeof(map));
memset(link, -, sizeof(link)); for(i=; i<m; i++)
{
scanf("%d %d", &u, &v);
map[u][v]=;
map[v][u]=;
}
int cnt=;
for(i=; i<=n; i++)
{
memset(vis, false, sizeof(vis));
cnt+=dfs(i);
}
printf("%d\n", cnt/ );
return ;
}