二分图

1、二分图定义

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

2、判定二分图

2.1 染色法

如果一个图所有点集构成的循环圈不为奇数，则改图为二分图。
所以我们可以用121的方法，为每一个结点标记1或2。同时每个相邻的结点，我们规定不能标记相同的数字。如果最后出现一个点既可以标记1，又可以标记2，则该图不为二分图。

2.2 例子

题目：染色法判定二分图
给定一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。

输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。

输出格式
如果给定图是二分图，则输出“Yes”，否则输出“No”。

数据范围
1≤n,m≤105

源代码

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

const int N=200010;

int n,m;
int e[N],h[N],ne[N],idx=0;
int group[N];

void add(int x,int y){
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}

bool dfs(int x,int y){
    group[x]=y;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!group[j]){
            if(!dfs(j,3-y)){
                return false;
            }
        }
        else{
            if(group[j]==y)
                return false;
        }
    }
    return true;
}

int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!group[i]){
            if(!dfs(i,1)){
                cout<<"No"<<endl;
                return 0;
            }   
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

3、求二分图的最大匹配

3.1 算法

匈牙利算法
具体思路：尽最大努力匹配左边的点。
1.如果存在匹配且不与之前的点冲突的点，则该点确定，继续判断下一个点。(递归出口)
2.如果存在匹配但与之前的点冲突的点，则返回到左边与该点冲突的点上(即当前与右边的点匹配的点)。递归用左边新的点与右边的点进行最大匹配。
3.如果该点实在找不到与之匹配，且用递归也找不到与之前的结点不冲突的点，则忽略该点，继续判断下一个点。

3.2 例子

题目：二分图的最大匹配
给定一个二分图，其中左半部包含n1个点（编号1_{n1），右半部包含n2个点（编号1}n2），二分图共包含m条边。数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。

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

数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105

源代码

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

const int N=100010;

int n1,n2,m;
int e[N],ne[N],h[N],idx=0;
bool vist[N];
int match[N];

void add(int x,int y){
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}

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

int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d%d",&n1,&n2,&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(vist,false,sizeof(vist));
        if(find(i))
            res++;
    }
    cout<<res<<endl;
    return 0;
}