首页 > 其他分享 >二分图判定

二分图判定

时间:2022-12-01 14:24:53浏览次数:40  
标签:二分 int 集合 num 判定 奇环 节点

二分图的判定

二分图的定义:若无向图\(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

相关文章

  • wqs 二分
    更应该说是一种思想吧。我们希望知道恰好选择\(k\)个物品时的答案,但世界上哪来的那么多恰好呢。令\(f_x\)是恰好选择\(k\)个物品时的答案,那么点集\((x,f_x)\)常会......
  • 双栈排序——二分图+模拟
    二分图建模-双栈排序题目描述Tom最近在研究一个有趣的排序问题。如图所示,通过\(2\)个栈\(S_1\)和\(S_2\),Tom希望借助以下\(4\)种操作实现将输入序列升序排序。......
  • 洛谷 P1387 最大正方形(前缀和,二分)
    题目分析当一个边长为x的正方形不包含0时,这个正方形内的二维前缀和为x*x,题目想求满足条件的最大的正方形的边长假如最大的正方形的边长为ans,那么凡是边长大于ans的正方形......
  • 二分浅入
    二分前言仅看要点不是很能理解,主要是看示例要点总结复习用要点关注范围,需要的是\([left,right]\)还是\([left,right)\)定义最后\(l\)和\(r\)落点位置是什么根......
  • 拓端tecdat|R语言代码编写对二分连续变量进行逻辑回归数据分析
    R语言对二分连续变量进行逻辑回归数据分析​教育或医学的标准情况是我们有一项连续的措施,但随后我们对那些具有临床/实践意义的措施有了切入点。一......
  • #yyds干货盘点# LeetCode程序员面试金典:判定字符是否唯一
    题目:实现一个算法,确定一个字符串s的所有字符是否全都不同。示例1:输入:s="leetcode"输出:false示例2:输入:s="abc"输出:true代码实现:classSolution{public......
  • 二分查找
    二分查找:请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。二分查找思路二分查......
  • NLP手札1. 金融信息负面及主体判定方案梳理&代码实现
    这个系列会针对NLP比赛,经典问题的解决方案进行梳理并给出代码复现~也算是找个理由把代码从TF搬运到torch。Chapter1是CCFBDC2019的赛题:金融信息负面及主体判定,属于实体关......
  • ACM预备队-week5(DFS/BFS/二分图)
    [蓝桥杯2013国C]危险系数题目链接:P8604[蓝桥杯2013国C]危险系数-洛谷|计算机科学教育新生态(luogu.com.cn)割点:删除这个顶点集合以所有顶点相关联的边以......
  • 二分查找-LeetCode704 简单题
    LeetCode代码链接:https://leetcode.cn/problems/binary-search/题目:给定一个 n 个元素有序的(升序)整型数组 nums和一个目标值 target ,写一个函数搜索 nums 中的t......