导读：什么是二分图？

二分图的顶点集V可分割为两个互不相交的子集A和B，而且图中的任意一条边的两个端点，都是一个端点属于集合A，另一个端点属于集合B。如下图：

二分图的特点/判断

一个图是二分图的充分必要条件是

​ 至少有两个顶点，而且要么没有回路，要么只有边数为偶数的回路。

​ 为了对这个结论有更具体的认识，我们举个例子看一下，下面先展示一个有环二分图。

[HTML_REMOVED]

​ 红色的就是环，大家可以尝试一下画环，你们会发现，只要是二分图，无论怎么造环，这些环的边一定是偶数的，如果你造出了奇数边的环，就说明你破坏了二分结构。你们想想，环肯定是连通两个集合的，集合A伸出一条边伸进集合B，集合B就一定要还一条边回来，一来一回必是偶数，如果出现了奇数那肯定是某集合内部联通了。

​ 有人会有疑问，但如果两个集合内部都联通了，那不也是偶数环吗？那还是二分图吗？

​ 看下图：

​ 不难发现，这样的图形其实也是二分图，只不过是点的位置误导了我们而已。

判断二分图的算法

​ 染色法是用于判断二分图的算法，算法流程如下：

• 步骤一：随便找一个连通块，随便找一个起点，将其染色。
• 步骤二：接着遍历这个连通块中的点，将这些点染成与相连点相反的颜色。
• 如果出现矛盾，说明不是二分图。
• 如果无矛盾：
  • 图中所有的连通块都染好色了，说明这个图是二分图。
  • 还有未染色的连通块，执行步骤一。

​ 接下来看代码实现模板(c++)

#include<iostream>
const int N = xxxxxx, M = xxxxxxx
//用邻接表存图模板，
//一般二分图都是无向图，所以存边要记得正反各存一次
int h[N],e[M],ne[M],idx;
void add(int a,int c)
{   
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void init()
{
    memset(h,-1,sizeof h);
}

//染色法模板
//color[k]=a,表示点k的颜色是a
int color[N];
//这个dfs的作用是，判断这样染色会不会出现矛盾
bool dfs(int u ,int c)
{
    color[u]=c;//先给自己染色再深搜
    //遍历与自己相连的点
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(!color[j])//如果这个点还未被染过色
            if(!dfs(j,3-c))//就染成相反色，调用dfs看看会不会矛盾(这里把1，2作为相反色)
                return false;
        else if(color[j]==c)
            return false;
    }
    return true;
}

为了更好记忆这个代码的步骤，下面简单模拟一下：

练习例题：染色法判断二分图

AC代码

#include<iostream>
#include<cstring>
using namespace std;
//无向图，存两条边，N*2
const int N = 2*100010;
int h[N],ne[N],e[N],w[N],idx;
//记录点的颜色 , 1 是黑色 ，2是白色
int color[N];
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int c)
{
    color[u]=c;//先染色!!!
    for(int i=h[u];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 = 0 ; i < m ;i ++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    bool flag = true;
    for(int i = 1 ; i<=n ;i ++)
    {
        if(!color[i])//no clor
            if(!dfs(i,1))//what ever color
            {
                flag  = false;
                break;
            }
    }

    if(flag) 
        puts("Yes");
    else
        puts("No");

    return 0;
}