二分图的判定
二分图的定义:若无向图\(G\)的所有节点可以划分为两个集合\(A,B\),若\(A,B\)均不为空且不存在一条边\((u,v)\)使得\(u,v\)属于同一集合,则称这个无向图为二分图。
通俗的说,就是两个集合各自内部没有边连接
定理:一张无向图是二分图,当且仅当图中不存在奇环.
证明:反证法:设图中存在奇环,则无论怎么划分,必然存在一条边使得两边节点属同一集合,与定义矛盾,假设不成立,原命题成立
而在无向图中寻找奇环,可以采用黑白染色的方法。具体地,对于每一个连通块,任选一个点作为源点,染成白色,然后继续扩展,对于白色的下一层节点染成黑色,对于黑色的下一层节点染成白色即可。若染色过程中发现当前点与已经染过色的后继结点颜色相同,证明存在奇环,此图不是二分图
代码如下:
void dfs(int u,int num){
c[u]=num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!c[v])dfs(v,num==1?2:1);
if(c[v]==c[u]){
puts("0");
exit(0);
}
}
}
//main中
for(int i=1;i<=n;i++)if(!c[i])dfs(i,1);
标签:二分,int,集合,num,判定,奇环,节点
From: https://www.cnblogs.com/oierpyt/p/16941289.html