一.二分图的基本知识

1.定义

G=(V, E)是一个无向图，若能将V分割成两个互不相关的点集X，Y，且图中每条边连接的两个顶点一个在 X中，另一个在 Y中，则称图G为二分图。

在这里插入图片描述
2.性质与判定

定理：当且仅当无向图G的每一个环的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数为 0，故也视为二分图。

判定方法：dfs23染色法

过程：我们把X部的结点颜色设为2，Y部的颜色设为3。
从某个未染色的结点u开始跑dfs。把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否相同，相同则不是二分图。
如果一个图不连通，则在每个连通块中作判定。

代码如下：（链式前向星存图）

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int M=N*N*2;
struct ppp{int u,v,next;
}e[M];
int vex[N],vis[N],k,flag=1;void add(int u,int v){k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}
void dfs(int u){for(int i=vex[u];i;i=e[i].next){int v=e[i].v;if(vis[v]==0){vis[v]=vis[u]^1;dfs(v);}else if(vis[v]==vis[u]){flag=0;}}
}
int main(){int n,m,u,v;cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v;add(u,v);}for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=2; dfs(i);}} return 0;
}

二.二分图最大匹配

什么是二分图最大匹配

定义二分图两部分的点分别称为左部点和右部点。
一张图的匹配是一些没有公共端点的边，最大匹配即没有公共端点的边的边数。
可以想象，对于一个二分图而言，显然一个匹配是对于每一个左部点，连一条边向一个右部点，或者不向右部点连边。但是每个左部点不会对应两个或以上的右部点。

怎么求二分图最大匹配

方法1：匈牙利算法

枚举每一个左部点u ，然后枚举该左部点连出的边，对于一个出点v，如果它没有被先前的左部点匹配，那么直接将u 匹配v，否则尝试让v的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将u 匹配v，否则u 失配。
尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。
个人理解匈牙利算法：判断是否能匹配第 i 个人，是在之前的所有匹配成功的左部点不会匹配不到人的前提下，尝试能不能让第 i 个点匹配到人。
时间复杂度：O(nm)

代码实现如下

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
struct ppp{int u,v,next;
}e[N*N]; 
int n1,n2,m;
int cp[N],vis[N],vex[N],k;void add(int u,int v) {k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}int dfs(int u,int tag) {//tag为时间戳，保证每次dfs点不重复经过 if(vis[u]==tag)return 0; vis[u]=tag;for(int i=vex[u];i;i=e[i].next){int v=e[i].v;if(!cp[v]||dfs(cp[v],tag)){//如果喜欢的人单身，直接在一起//如果喜欢的人有对象，让他对象再找一个对象；//1.如果找得到，喜欢的人的对象换掉，喜欢的人成为自己的对象//2.如果找不到，这个喜欢的人就没机会了(找下一个喜欢的人) cp[v]=u;return 1;}}return 0;
}int main() {int u,v;cin>>n1>>n2>>m;for (int i=1;i<=m;i++) {cin>>u>>v;add(u,v);}int ans=0;for (int i=1;i<=n1;i++) {if (dfs(i, i))++ans;//让左部点 i去找对象 }cout<<ans;return 0;
}