二分图

构建二分图当且仅当不含奇数环

• 染色法

• 匈牙利算法

染色法判断二分图

如果是二分图的话，说明我们可以讲点进行均等分，也就是说我们一定不能出现奇数环

染色法主要是用1 和 2 对图中的每一个点进行标记颜色，如果出现颜色间隔相同，或者一些矛盾的情况，那么说明不是二分图

bool dfs(int u,int v) {	
    color[u] = v; //染色
    for(int i = h[u];i != -1;i = ne[i]) { //从起点出发，将所有点进行染色
        int j = e[i]; 
      	//if判断当前结点是否被染色
        if(!color[j]) { 
          	//将这个点的颜色染成相反的颜色
            if(!dfs(j,3 - v)) return false;
        }else if(color[j] == v) return false; //如果发现当前颜色和前一个颜色相同说明冲突，返回false
    }

    return true;
}

匈牙利算法

匈牙利算法又名找唯一对象算法

主要使用来解决匹配问题

保证二分图两边互相匹配，并且不会出现脚踏两只船的情况

常见题型

给定一个二分图，其中左半部包含 n1n1 个点（编号 1∼n11∼n1），右半部包含 n2n2 个点（编号 1∼n21∼n2），二分图共包含 mm 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

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

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

st数组的含义

st数组主要是用来判断妹子是否有合适的对象，每一次初始化st数组主要是为了执行st[j]里面判断这个妹子的对象是否有备胎的情况
如果不进行初始化的话，遍历后面的男的话，看到妹子(st)都被占有，一点争取的机会都没有了。。。

find(match[j])解释

这种情况的前提是这个妹子已经和别人匹配了，我们此时遍历的这个人也想追求她，于是想要尝试让与他配对的男的去寻找备胎

j代表的是这个妹子，match[j]代表的是与这个妹子处的另一个男的，再从这个男的出发，当然不会出现又去遍历那个妹子的情况，因为st[j]此时被最开始的男的占用了，直到找到没有被匹配的妹子为止

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010;
int n1,n2,m;

int e[M],h[N],ne[M],idx;
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) {
    for(int i = h[x];i != -1;i = ne[i]) {
        int j = e[i];
        if(!st[j]) {
            st[j] = true;
          	//如果找的对象没有和别人匹配过或者是有和别人匹配过但是别人有备胎
            if(match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n1 >> n2 >> m;

    memset(h,-1,sizeof(h));
    while(m--) {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    int res = 0;
  //遍历一边即可
    for(int i = 1;i <= n1;i++) {
        memset(st,false,sizeof(st));
      	//find函数判断是否找到了合适的对象
        if(find(i)) res++;

    }

    cout << res << endl;
    return 0;
}