染色法判二分图

//二分图：图中不含奇数环  一条边两个点的颜色需不同 
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int col[N];
int n,m;

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

bool dfs(int k,int s)
{
	col[k]=s;
	for(int i=h[k];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!col[j])
		{
			if(!dfs(j,3-s))return false;   //若染色矛盾 返回错误 
		}
		else if(col[j]==s)return false;   //矛盾：边上两点颜色一样 
	}
	return true;
}

int main(void)
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	
	bool fa=false;
	for(int i=1;i<=n;i++)
	{
		if(!col[i])
		{
			if(!dfs(i,1))
			{
				fa=true;
				break;
			}
		}
	}
	if(fa)
	puts("No");
	else
	puts("Yes");
	return 0;
 }