AcWing 860. 染色法判定二分图
原题链接
简单
作者:
晓龙coding
,
2021-12-16 16:12:12
,
所有人可见
,
阅读 177
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200010;
int e[N], ne[N], h[N], idx, color[N];
bool res = true;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int col) {
color[u] = col;
for (int i = h[u]; i != -1; i = ne[i]) {
if (!color[e[i]]) dfs(e[i], 3 - col);
else if (color[e[i]] == col) {
res = false;
return;
}
}
}
int main() {
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++) {
if (!color[i]) {
dfs(i, 1);
}
if (!res) break;
}
if (res) cout << "Yes";
else cout << "No";
return 0;
}