AcWing 860. 染色法判定二分图
原题链接
简单
作者:
Coinisi.
,
2022-02-24 22:05:34
,
所有人可见
,
阅读 103
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;
int e[M],idx,h[N],ne[M];
int st[N];
void add(int a,int b)
{
e[idx]=b, ne[idx]=h[a],h[a]=idx ++;
}
bool dfs(int u,int c)
{
st[u]=c;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(st[j] == false)
{
if(dfs(j,3-c) == false )
return false;
}
else if(st[j] == c) return false;
}
return true;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
bool flag=true;
for(int i=1;i<=n;i++)
{
if(st[i] == false)
{
if(dfs(i,1) == false)
{
flag=false;
break;
}
}
}
if(flag == true) puts("Yes");
else puts("No");
return 0;
}