AcWing 860. 前向星染色法
原题链接
简单
作者:
越狱
,
2019-10-04 01:15:42
,
所有人可见
,
阅读 957
C++ 代码
#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
struct Edge
{
int to;
int next;
};
const int N = 2e5 + 2;
int head[N],color[N];
Edge edge[N];
int cnt = 0;
void add(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
bool dfs(int u, int c)
{
color[u] = c;
for(int i=head[u]; i!=-1; i = edge[i].next)
{
int j = edge[i].to;
if(color[j] == c)
return false;
if(!color[j] && !dfs(j,-c))
return false;
}
return true;
}
int main()
{
int n,m;
cin>>n>>m;
memset(head, -1, sizeof(head));
memset(color, 0, sizeof(color));
while(m--)
{
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1; i<=n; ++i)
{
if(!color[i])
{
if(!dfs(i,1))
{
cout<<"No"<<endl;
return 0;
}
}
}
cout<<"Yes"<<endl;
return 0;
}