AcWing 860. 染色法判定二分图
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-19 15:56:35
,
所有人可见
,
阅读 200
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool dfs(int u, int c)
{
//首先来记录当前的这个点的颜色是c
color[u] = c;
//然后依次来遍历当前这个节点的所有的邻接顶点
for (int i = h[u]; i != -1; i = ne[i])
{
//取得这个邻接顶点的编号
int j = e[i];
//如果当前的这个节点没有被染色, 此时执行下面的
if (!color[j])
{
//此时将这个点进行染色, 染成另外的一种颜色
if (!dfs(j, 3 - c)) return false;
}
//如果此时j已经染过颜色, 此时只要进行一次判断就可以了
//如果j编号节点的颜色与当前的节点的颜色是相同的, 此时直接返回的是false;
else if (color[j] == c) return false;
}
//
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
//使用flag来表示在染色的过程中是否有矛盾产生。
bool flag = true;
for (int i = 1; i <= n; i ++) {
if (!color[i]) {
//此时表示第i个节点没有被染色
//如果在dfs的过程中返回了一个false, 此时表示发生了矛盾, 此时将这个位置上染成第一种颜色
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
//如果flag表示的是true, 表示的是在整个的过程中是没有矛盾发生的,
if (flag) puts("Yes");
else puts("No");
return 0;
}