二分图当且仅当一个图中不含奇数环
1.染色法
简单来说，将顶点分成两类，边只存在于不同类顶点之间，同类顶点之间没有边。
e.g.
如果判断一个图是不是二分图？
开始对任意一未染色的顶点染色。
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。
bfs和dfs可以搞定！
注意：如果有三个点另外成环，整个环是一个孤立环，其他都满足二分图，但是这个孤立不满足二分图，二分图的点不一定连通。所以要遍历每一个点。
1.dfs思路：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];
void add(int a, int b)//邻接表插入点和边
{
e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool dfs(int a,int c){
color[a]=c;
for(int i=h[a];i!=-1;i=ne[i]){
int j=e[i];
if(!color[j]){
if(!dfs(j,3-c)){
return false;
}
}
else{
if(color[j]==c){
return false;
}
}
}
return true;
}
int main(){
memset(h, -1, sizeof h);//初始化邻接表
cin >> n >> m;
for(int i = 1; i <= m; i++)//读入边
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,1)){
puts("No");
return 0;
}
}
}
puts("Yes");
return 0;
}2.bfs思路：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];
queue<int> q;
void add(int a, int b)//邻接表插入点和边
{
e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool bfs(int a){
color[a]=1;
q.push(a);
while(q.size()){
auto t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!color[j]){
color[j]=3-color[t];
q.push(j);
}
else if(color[j]==color[t]) return false;
}
}
return true;
}
int main(){
memset(h, -1, sizeof h);//初始化邻接表
cin >> n >> m;
for(int i = 1; i <= m; i++)//读入边
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for(int i=1;i<=n;i++){
if(!color[i]){
if(!bfs(i)){
puts("No");
return 0;
}
}
}
puts("Yes");
return 0;
}
2.匈牙利算法
要了解匈牙利算法必须先理解下面的概念：
匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
这篇文章把这个算法讲的很有意思：
趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN博客
简单来说就是：
遍历所有男生
让该男生考虑所有心动女生
如果当前女生单身，或者该女生的对象找了备胎，该女生就接受该男生
最坏时间复杂度 O(nm)，和其它最大流问题一样，实际比较快
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[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]=1;
if(match[j]==0||find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
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 res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
printf("%d\n", res);
return 0;
}
在上述代码中，有一个令人费解的东西：就是st数组的作用，其实直白的理解：如果你每次不把st重新置为false，那剩下的人一看到前面的妹子st已经为true，不去让妹子的对象换掉这个妹子，直接就放弃了，会影响最后结果。
我们通过一个实际案例理解一下：
不难看出，st数组主要是在两个人连接了一个妹子的的时候才有用， 这个st的存在，让find在本次找的时候，原来的那个男生，不会再找这个妹子，只会找其他的。
还有一种理解：st的理解可以参考操作系统中锁的概念。假如说左边的是进程，右边的是资源。当进程i要访问资源j时，为了避免其他进程在此时访问资源j，需要对资源j加一个“锁”，即st[j] = true。当进程i访问完资源时，为了让后续其他进程也能访问资源，需要把锁解开，即memset(st, false, sizeof st)。
