AcWing 860. 染色法判定二分图
原题链接
简单
作者:
风起于浮萍之末
,
2024-01-28 10:47:05
,
所有人可见
,
阅读 38
#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;// e和ne数组都是针对于边的
int color[N];// 某个点的颜色
void add(int a,int b){// 创造a--》b
e[idx]=b; //相当于创建一个节点
ne[idx]=h[a];// 改变后指针 h[a]为以a为节点的第一个指向节点
h[a]=idx++;// 先指向 后++
//因为是头插法
}
bool dfs(int u,int c){
color[u]=c;//u这个节点的颜色为c
for(int i=h[u];i!=-1;i=ne[i]){//这个是遍历所有以u为入度的出边
int j=e[i];// 上一步都是获取的下标
if(!color[j]){//临边节点没有染色
if(!dfs(j,3-c)) return 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);// 无向图加边 不用特别考虑重边
}
bool flag=true;//标志位
for(int i=1;i<=n;i++){//点是从1开始的
if(!color[i]){// 没有被染过
if(!dfs(i,1)){// 如果有问题就停止
flag=false;
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}