在图论中,把相邻定点染成不同颜色的问题叫做图着色问题。对图进行染色所需要的最小颜色数称为最小着色数。
把最小着色数是2的图称为二分图。

code:

#include <cstdio>
#include <vector>

const int MAX_V = 1000 + 7; // 定点最大个数
using namespace std;

vector<int> g[MAX_V];   // 邻接表
int color[MAX_V];       // 顶点i的颜***ool dfs(int v, int c)
{
    color[v] = c;       // 把顶点染成颜色c
    for(int i=0; i<g[v].size(); i++)    // 查询与这个顶点相邻的顶点
    {
        if(color[g[v][i]] == c)         // 如果相邻的顶点也为c,则染色不成功
            return false;
        if(color[g[v][i]] == 0 && !dfs(g[v][i], -c))    // 相邻的顶点没有染色,就染成-c,并判断能否染色成功
            return false;
    }
    return true;
}

int main()
{
    int V;                  // 顶点个数
    int a, b;       // a->b有一条边
    scanf("%d", &V);
    for(int i=0; i<MAX_V; i++)
        g[i].clear();   // 清空邻接表
    while(scanf("%d%d", &a, &b) != EOF)
    {
        g[a].push_back(b);  // 无向图
        g[b].push_back(a);
    }
    for(int i=0; i<V; i++)
    {
        if(color[i] == 0)
        {
            if(!dfs(i, 1))  // 如果顶点还没有染色,就染色成1
            {
                printf("No\n");
                return;
            }
        }
    }
    printf("Yes\n");



    return 0;
}

如果是连通图,那么一次dfs就可以访问到所有的顶点。如果题目描述中没有说明,那么有可能图不是连通的,
这样就需要依次检查每个顶点是否访问过。