下面的标程从《啊哈!算法》摘录! 我给每句话都加了注释
《啊哈!算法》是一本写非常非常非常好的书!!!强烈推荐!!!
#include<cstdio>
int e[101][101],match[101],vis[101],n,m;//match用来记录配对关系,例如v和u点配对成功,就记录match[v]=u,match[u]=v
int dfs(int cur){
for(int i=1;i<=n;i++){//尝试每个点
if(vis[i]==0&&e[cur][i]==1){//尝试每个没有访问过,且和cur联通的点
vis[i]=1;//标记已访问过
if(match[i]==0||dfs(match[i])==1){//如果i点未匹配或向下dfs i的配对点后找到了新的匹配
match[i]=cur;//更新配对关系
match[cur]=i;//更新配对关系
return 1;//表明已找到,返回1
}
}
}
return 0;//全部搜索完了,没找到,返回0
}
int main(){
int t1,t2,sum=0;
scanf("%d %d",&n,&m);//n个点m条边
for(int i=1;i<=m;i++){
scanf("%d %d",&t1,&t2);
e[t1][t2]=1;//无向图
e[t2][t1]=1;
}
for(int i=1;i<=n;i++) match[i]=0;//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) vis[j]=0;//清空上次搜索的标记
if(dfs(i)==1) sum++;//寻找增广路,匹配成功,配对数+1
}
printf("%d",sum);
return 0;
}