AcWing 860. 染色法判定二分图
原题链接
简单
作者:
C___
,
2021-12-05 21:22:33
,
所有人可见
,
阅读 137
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int idx, n, m, e[N<<1], ne[N<<1], h[N];
int st[N];
void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
bool dfs(int x, int c) {
st[x] = c;
for(int i = h[x]; ~i; i = ne[i]) {
int son = e[i];
if(!st[son]) { if(!dfs(son, 3 - c)) return false; }
else if(st[son] == c) return false;
}
return true;
}
int main(void) {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++) {
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]) {
flag = dfs(i, 1);
if(!flag) break;
}
flag ? puts("Yes") : puts("No");
return 0;
}