C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010,M=2*N;
int color[N];//表示这里的统计的颜色
int h[N],idx;
int n,m;
struct edge
{
int v,ne;//表示它的相邻的结点和相邻的下一条边
}e[M];
void Add(int a,int b)
{
e[++idx]={b,h[a]};
h[a]=idx;
}
bool dfs(int v,int u)//v表示下一个结点,u表示颜色
{
color[v]=u;
//然后从v这个结点开始进入
for(int i=h[v];i;i=e[i].ne)
{
int j=e[i].v;//找出这个点
if(!color[j])//如果j这个结点没有染色的话,我们将其染个颜色
{
if(dfs(j,3-u))
{
return 1;//如果这里为奇数环的话,就一直返回1
}
}
else if(color[j]==u)
{
return 1;//如果这里的颜色发生冲突的话,我们也返回1
}
}
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
Add(a,b);
Add(b,a);//因为是无向图,因此要加上两次
}
bool flage=false;
for(int i=1;i<=n;i++)//这里防止这里的图不连通
{
if(!color[i])
if(dfs(i,1))
{
flage=true;
break;//如果有奇数的环,我们就跳出
}
}
if(flage)
{
puts("No");
}
else
{
puts("Yes");
}
return 0;
}