二分图就是可以把所有点划分到两边集合中去，使得所有的边在两个集合外且在两个集合之间，集合内部没有边的图。
二分图的性质：当且仅当图中不含有奇数环。
（奇数环：环中边的数量是奇数）
证明：
必要性：二分图中不含有奇数环。
反证法。
假设有一个奇数环是二分图，设有两个集合A，B。
第1、3、5…个点在A中，第2、4、6个点在B中。由于是二分图，且起点（1号点）在A中，则最后一个点一定在B中。那么点的数量一定为偶数，与假设相矛盾。
因此二分图不会含有奇数环。
充分性：若一个图不含有奇数环，则它是二分图。
构造法。
假设有一个图不含奇数环，设有两个集合A，B。
遍历图，若遇到一个点没有被加入集合中，则把它放进A集合，把与这个点相连的所有点放入B集合。（则一条边的两个点不会在同一个集合，这是一个染色的过程）
则，图中任意一点的颜色确定了，则整个图的颜色都确定了。
由于图中不含有奇数环，整个染色过程不会有矛盾。（也可以反证法）
也就是说，如果一个图可以用染色法染一遍且没有矛盾发生，则它是二分图；若出现了矛盾，则它不是二分图。
染色法模板：
for(int i=1;i<=n;i++)
if(i没有被染色)
dfs(i);
注意：
存图用链式前向星。
用memset(h,-1,sizeof(h))来初始化。
（虽然memset是按位赋值的，但由于这里赋值的参数是-1，总的值也是-1，不信可以试试）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int N=1e5+10,M=2*N;
int n,m;
int e[M],ne[M],h[N],idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int flag;
int st[N];//每个点的颜色：1 2
void dfs(int u,int c)
{
if(flag) return;
st[u]=c;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]) dfs(j,3-c);
else if(st[j]==c)
{
flag=1;return;
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(h));//链式前向星的初始化
fir(i,1,m)
{
int a,b;cin>>a>>b;
add(a,b);add(b,a);
}
flag=0;
for(int i=1;i<=n;i++)
{
if(flag) break;
if(!st[i]) dfs(i,1);
}
if(flag) cout<<"No";
else cout<<"Yes";
return 0;
}
在一个比较快的时间内告诉我们左右的匹配成功最大的数量。
匹配指的是边。匹配成功指的是不存在两条边共用一个点。
通俗的理解：
如图，有四个男生和四个女生，最多可以成功多少对恋爱关系使得不存在脚踏多只船的情况？
算法思路：（如图）
时间复杂度：O(n*m)
注意：存边的时候只需要存左边指向右边即可。
因为遍历的是所有左边的点，需要判断的是左边指向右边的点是否已匹配。不需要用到右边指向左边的点。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(i,a,n) for(int i=a;i<=n;i++)
const int N=500+10,M=1e5+10;
int n1,n2,m;
int h[N],e[M],ne[M],idx;//h是点，e和ne是边
int match[N];//右边的点所匹配的左边的点
int st[N];//该点是否已经访问过
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int find(int x)//为x点找匹配的点
{
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=1;
//核心
if(!match[j]||find(match[j]))//该点没有匹配 或匹配的对象可以重新匹配
{
match[j]=x;
return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof(h));
while(m--)
{
int a,b;scanf("%d%d",&a,&b);add(a,b);
}
int ans=0;
for(int i=1;i<=n1;i++)//遍历每一个左集合
{
memset(st,false,sizeof(st));
if(find(i)) ans++;
}
cout<<ans;
return 0;
}