二分图——二分图最大匹配

时间:2021-05-21 06:14:16

下面的标程从《啊哈!算法》摘录! 我给每句话都加了注释
《啊哈!算法》是一本写非常非常非常好的书!!!强烈推荐!!!


#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;
}