二分图判定模板

把相邻顶点染成不同颜色的问题叫做图着色问题。

对图进行染色所需要的最小颜色数称为最小着色数。

最小着色数是2的图称作二分图。

#include <cstdio>
#include <cstring>

using namespace std;

#define max_v 1010

vector <int> G[max_v];

int color[max_v];
int V;

bool dfs(int v,int c)
{
    color[v]=c;
    for(int i=0;i<G[v].size();i++)
    {
        if(color[G[v][i]]==c) return false;
        if(color[G[v][i]]==0 && !dfs(G[v][i],-c)) return false;
    }
    return true;
}

void solve()
{
    for(int i=0;i<V;i++)
    {
        if(color[i]==0)
        if(!dfs(G[i],1))
        {
           
       
            printf("No ");
            return ;
        }
    }
    printf("Yes ");
}