二分图

有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！

说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

染色法

判断给定图 是否是二分图
算法步骤：

1. 循环对每个点进行染色（dfs或者bfs）
2. 判断其相邻的点中，若未染色则将其染上和当前顶点不同的颜色。
3. 若已经染色 且颜色跟当前点颜色一样的则说明不是二分图，如果没有则进行下一个节点的判断

匈牙利算法

计算二分图的最大匹配数

二分图的匹配：给定一个二分图 G ，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

算法思想：
find(x) : 左半边点x的某条边的右半边的另一个点
match[j] 右半边的点j所匹配的点

1. 对左半边图的节点进行循环
   • 循环该节点所有的边(find(x))，如果能够在右半边找到一个没有匹配过的点（match[j] == 0），则进行匹配
   • 如果找到的点已经匹配上了别的点了(match[j] != 0)，则看其匹配的点是否有别的备胎（find(match[j])）
   • 有备胎则将匹配取消，让其去找备胎。
   • 如果能够成功匹配则返回true （总匹配边数 res++）
   • 如果无备胎，则返回false

tips:

1. 循环中找每个点对应右半边点前都要先重置st数组为false
2. 要用st数组来标记节点是否被访问过了

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;
const int M = 1e5+10;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
//st 标记节点是否递归找过， match[x]：和 x 编号的男生的编号
bool st[N];
int match[N];

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

bool find(int x){
    //i指代的是下标为idx的边
    for(int i=h[x];i!=-1;i=ne[i]){
        int j = e[i];
        //递归的剪枝操作，如果没有的话会报MLE
        if(!st[j]){
            st[j] = 1; //标记该节点已经找过了
            if(!match[j] || find(match[j])){
                match[j] = x;
                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;
    for(int i=1;i<=n1;i++){
        memset(st,0,sizeof(st));
        if(find(i)){
            res++;
        }
    }
    cout << res;
    return 0;
}