AcWing 860. 染色法判定二分图
原题链接
简单
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn= 1e5 +5;
int n,m,head[maxn],color[maxn],tol;
struct node{
int to,next;
}edge[maxn*2];
void add(int u,int v)
{
edge[tol].to = v;
edge[tol].next = head[u];
head[u] = tol++;
}
bool dfs(int u , int c)
{
color[u] = c;
for(int i = head[u] ; i != -1 ; i = edge[i].next)
{
node e = edge[i];
if(!color[e.to])
{
if(!dfs(e.to,3-c))
return false;
}
else
{
if(color[e.to] == c)
return false;
}
}
return true;
}
int main()
{ memset(head,-1,sizeof(head));
scanf("%d%d", &n, &m);
tol = 0;
for (int i = 1; i <= m; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
bool flag = true;
for (int i = 1; i <= n; i ++ )
{ if(!color[i])
{
if(!dfs(i,1))
{flag = false;
break;
}
}
}
if(flag)
puts("Yes");
else
puts("No");
}