题目描述
奇数环:一个环,且有奇数条边;
什么样的图是二分图 ; 一个图是二分图,当且仅当这个图没有奇数环;
我们可以通过对一个图进行染色判断这个图是不是二分图,规定一条边上的两个端点不颜色不能相同,只要满足这个性质就是二分图,染色的过程可以通过深度搜索完成。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N =100010,M = 100010 * 2;
int n,m;
int e[M], ne[M], idx, h[N];
int color[N];
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;//把当前这个点染色为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()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
scanf("%d %d",&a,&b);
add(a, b), add(b, a);
} //图的初始化;
bool flag; //用来判断图最终是否能够染色为二分图;
for(int i = 1; i <= n; i ++) //从第一个点开始检查是否每一个点都染色成功了;
if(!color[i])//如果当前这个点还没有染色;
{
if(!dfs(i,1))//那就把当前这个带你染色为1;这时起始点也是被染色为1;
{
flag = false ;//如果染色失败,就让flag变为false;
break;
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}