当前位置:网站首页>二分图判定
二分图判定
2022-07-06 14:26:00 【AC__dream】
先来说一下什么是二分图,对于一个图,我们将其顶点集分为两部分A和B,从而使得任意一条边的两个顶点一个在A中一个在B中,而不会出现一条边的两个顶点全部在A中或全部在B中这种情况。
先来说一个定理:一个图是二分图当且仅当这个图中不存在奇数环,也就是不存在一个环的顶点个数是奇数个。
如果利用这个定理来判定一个图是不是二分图的话那么我们就可以使用染色的方法来进行实现,就是每一条边的两个顶点的颜色一定是不相同的,我们按照这个原则来对图进行染色,如果染色成功那么这个图就是一个二分图,否则就不是一个二分图。
给出一道例题及其代码实现:
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int N=2e5+10;
int h[N],e[N],ne[N],color[N],idx;
//color[i]代表第i个节点的颜色
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
bool dfs(int x,int c)
{
color[x]=c;
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(color[j]!=-1)//j节点已经染过颜色
{
if(color[j]==c) return false;//一条边的两个顶点颜色相同,矛盾
}
else if(!dfs(j,c^1)) return false;//发现矛盾
}
return true;//所有节点都没有发现矛盾就返回真
}
int main()
{
int n,m;
cin>>n>>m;
memset(h,-1,sizeof h);
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
memset(color,-1,sizeof color);//初始颜色为-1
bool flag=true;
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
if(!dfs(i,1))//将当前点染成1号颜色
{
flag=false;//出现奇数环就直接退出
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}
边栏推荐
- Data processing skills (7): MATLAB reads the data in the text file TXT with mixed digital strings
- GPS从入门到放弃(十四)、电离层延时
- Seata聚合 AT、TCC、SAGA 、 XA事务模式打造一站式的分布式事务解决方案
- Force buckle 575 Divide candy
- [leetcode daily clock in] 1020 Number of enclaves
- 2021 geometry deep learning master Michael Bronstein long article analysis
- Report on technological progress and development prospects of solid oxide fuel cells in China (2022 Edition)
- LeetCode刷题(十一)——顺序刷题51至55
- 414. The third largest digital buckle
- PVL EDI project case
猜你喜欢
GPS from getting started to giving up (XV), DCB differential code deviation
Assembly and Interface Technology Experiment 6 - ADDA conversion experiment, AD acquisition system in interrupt mode
GPS from getting started to giving up (19), precise ephemeris (SP3 format)
Xiaoman network model & http1-http2 & browser cache
GPS from entry to abandonment (XIV), ionospheric delay
【sciter】: 基于 sciter 封装通知栏组件
硬件开发笔记(十): 硬件开发基本流程,制作一个USB转RS232的模块(九):创建CH340G/MAX232封装库sop-16并关联原理图元器件
Memorabilia of domestic database in June 2022 - ink Sky Wheel
重磅新闻 | Softing FG-200获得中国3C防爆认证 为客户现场测试提供安全保障
Chapter 3: detailed explanation of class loading process (class life cycle)
随机推荐
Codeforces Round #274 (Div. 2) –A Expression
Spatial domain and frequency domain image compression of images
【10点公开课】:视频质量评价基础与实践
BarcodeX(ActiveX打印控件) v5.3.0.80 免费版使用
Data processing skills (7): MATLAB reads the data in the text file TXT with mixed digital strings
二叉(搜索)树的最近公共祖先 ●●
解决项目跨域问题
中国1,4-环己烷二甲醇(CHDM)行业调研与投资决策报告(2022版)
3DMax指定面贴图
Some problems about the use of char[] array assignment through scanf..
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
GPS from getting started to giving up (XVIII), multipath effect
GPS from entry to abandonment (XIV), ionospheric delay
AI enterprise multi cloud storage architecture practice | Shenzhen potential technology sharing
GPS du début à l'abandon (XIII), surveillance autonome de l'intégrité du récepteur (raim)
GPS从入门到放弃(十六)、卫星时钟误差和卫星星历误差
做接口测试都测什么?有哪些通用测试点?
小常识:保险中的“保全”是什么?
11、 Service introduction and port
[leetcode daily clock in] 1020 Number of enclaves