在图论中,把相邻定点染成不同颜色的问题叫做图着色问题。对图进行染色所需要的最小颜色数称为最小着色数。
把最小着色数是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就可以访问到所有的顶点。如果题目描述中没有说明,那么有可能图不是连通的,
这样就需要依次检查每个顶点是否访问过。