首先来说一下什么是二分图。

二分图

二分图又称作二部图，是图论中的一种特殊模型。
设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。

性质

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

判断是否是二分图

这里我们用到染色法，用两种颜色来染这个图。如果该节点的颜色是0，那么所有与其相邻的节点的颜色都是1。最后判断是否满足上述条件即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010,M=2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int x,int c) //判断x点染c颜色对不对。
{color[x]=c; //给x染c色。 c=1,2for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!color[j]) //如果j点未被染色，判断它染另一种颜色是否合适。{if(!dfs(j,3-c)) return false; //c=1时候，另一种颜色为3-1=2}else if(color[j]==c) return false; //如果j点与x点颜色相同返回false}return true;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while(m--){int x,y;cin>>x>>y;add(x,y),add(y,x);}bool flag=true;for(int i=1;i<=n;i++) //从1点开始，将未被染色的点染上1颜色。{if(!color[i]){if(!dfs(i,1)){flag=false;break;}}}if(flag) puts("Yes");else puts("No");return 0;
}

二分图最大匹配

首先什么是匹配： 给定一个二分图G，在G的一个子图M中， M的边集{E}中的任意两条
边都不交汇于同一个结点，则称M是一个匹配。

然后如何求出最大匹配？这里有一个很经典的算法：匈牙利算法。

算法流程：

1.从任意一个没有被配对的点x开始，从点x的边中任意选一条边。如果此时点i没有被配对那么配对成功，则找到了一条增广路。如果点i此时已经被配对了，那么可以尝试将点i与其他点配对。如果尝试成功，则找到一条增广路。这里用match[ ]来记录配对关系， 即match[i] = x。 并且将配对数+1。 这个过程我们用dfs来实现。

2.如果配对失败，就从点x的边中重选一条边尝试。直到点x配对成功或尝试完x所有的边。

3.接下来对没有配对的点一一进行配对，直到所有的点都尝试完毕找不到新的增广路。

#include<bits/stdc++.h>
#define re register int
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}return x*f;
}
int n,m,tot;
const int M = 5e4+10;
int head[M],vis[M],match[M];
int cnt,ans;
struct edge{int to,nxt;
}e[M];
void add(int u,int v){e[++cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;
}
bool find(int x){for(re i(head[x]) ; i ; i=e[i].nxt){int v=e[i].to;if(!vis[v]){ //如果这个点没有被访问过vis[v] = 1;if(!match[v]||find(match[v])){ //如果这个点没有匹配，//或者这个点匹配的点可以去匹配另一个点match[v]=x; //就把这个点跟x匹配return 1;}}}return 0;
}
signed main(){n=read(),m=read(),tot=read();for(re i(1) ; i<=tot ; ++i){int u,v;u=read(),v=read();add(u,v);}for(re i(1) ; i<=n ; ++i){memset(vis,0,sizeof(vis));if(find(i)) ans++; //记录最大匹配数}printf("%d",ans);return 0;
}