acwing 题解交流群:AcChat私聊我,拉你进群。
什么叫二分图
-
有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边直接相连接!
-
说人话的定义:图中点通过移动能分成左右两部分,左侧的点只和右侧的点相连,右侧的点只和左侧的点相连。
-
下图就是个二分图:
- 下图不是个二分图:
如果判断一个图是不是二分图?
-
开始对任意一未染色的顶点染色。
-
判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色。
-
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断。
-
bfs和dfs可以搞定!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色,0 未染色,1 是红色,2 是黑色
int n, m;//点和边
void add(int a, int b)//邻接表插入点和边
{
e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool dfs(int u, int c)//深度优先遍历
{
color[u] = c;//u的点成 c 染色
//遍历和 u 相邻的点
for(int i = h[u]; i!= -1; i = ne[i])
{
int b = e[i];
if(!color[b])//相邻的点没有颜色,则递归处理这个相邻点
{
if(!dfs(b, 3 - c)) return false;//(3 - 1 = 2, 如果 u 的颜色是2,则和 u 相邻的染成 1)
//(3 - 2 = 1, 如果 u 的颜色是1,则和 u 相邻的染成 2)
}
else if(color[b] && color[b] != 3 - c)//如果已经染色,判断颜色是否为 3 - c
{
return false;//如果不是,说明冲突,返回
}
}
return true;
}
int main()
{
memset(h, -1, sizeof h);//初始化邻接表
cin >> n >> m;
for(int i = 1; i <= m; i++)//读入边
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for(int i = 1; i <= n; i++)//遍历点
{
if(!color[i])//如果没染色
{
if(!dfs(i, 1))//染色该点,并递归处理和它相邻的点
{
cout << "No" << endl;//出现矛盾,输出NO
return 0;
}
}
}
cout << "Yes" << endl;//全部染色完成,没有矛盾,输出YES
return 0;
}
每次看海绵哥的原理都很省事,省的我去搜orz
海绵哥yyds
请问
if(!dfs(b, 3 - c)) return false
这一句,如果没染色不就递归把相邻点染了吗,那为啥还要返回false,而不是true成功染色?
海绵哥题解真的清晰直观
请问为什么很多题不用头文件
#include <algorithm>
也能ac,为什么很多题解里都还是会带上这个头文件呢?良好习惯(狗头)
你题解写的真好。
orz
大佬问一下 如果存在自环的话 那不就是自己和自己相邻吗?也就是存在自环的不是二分图是吧
是的
自环也可以看成奇数环,边数是1,也是奇数
什么情况是不可以将下一个点成功染色从而返回false呢
我的理解是if(!dfs(b, 3 - c)) return false;这句不是用来判断下个点不能成功染色而返回false,因为下一个点没染色的话一定能染成另一种颜色,这句话是用来判断是否矛盾的,就下面那个else if里的内容,如果矛盾会返回false,if(!dfs(b, 3 - c)) return false;if里是如果返回了false会一直返回false直到最外层也返回false,就会在main函数里判断出false。
感谢佬,已经懂了,orz
英雄所见略同
确实,只要后续有一个点不满足染色条件就一直返回false
大哥 tql
tql海绵宝宝
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N=100010;
int n,m;
int h[N],ne[N],e[N],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 r)//当前点 当前点要染的颜色
{
color[u]=r;
}
int main()
{
memset(h,-1,sizeof(h));
}
在idedubug下,容易找到原因。
为什么我的深搜就超时了
tql
爱了爱了
这个太强了,真的喜欢
https://blog.csdn.net/WJPnb1/article/details/126332263?spm=1001.2014.3001.5501 第一次写csdn博客,写了这个找二分图最大匹配的,大家可以来看看,有问题交流交流
赞
😘
复习起来很有用,感谢整理
代码更好理解,hh,加油
建议图给的简单易懂,这样太耗眼了,hh
如何改变题解中图片大小,求大佬给下方法