当前位置:网站首页>Bipartite graph determination
Bipartite graph determination
2022-07-06 22:47:00 【AC__ dream】
First, let's talk about what is a bipartite graph , For a picture , We divide its vertex set into two parts A and B, Thus, one of the two vertices of any edge is A One of them is in B in , Instead of having two vertices of an edge all in A In or all of B In this case .
Let's start with a theorem : A graph is a bipartite graph if and only if there are no odd rings in this graph , That is, there is no ring with an odd number of vertices .
If we use this theorem to determine whether a graph is a bipartite graph, then we can use the method of coloring to realize , The color of the two vertices of each edge must be different , We dye the graph according to this principle , If the coloring is successful, then this graph is a bipartite graph , Otherwise, it is not a bipartite graph .
Give an example and its code implementation :
sample input :
4 4
1 3
1 4
2 3
2 4
sample output :
Yes
Code :
#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] On behalf of the i Color of nodes
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 Nodes have been dyed
{
if(color[j]==c) return false;// Two vertices of an edge have the same color , contradiction
}
else if(!dfs(j,c^1)) return false;// Find contradictions
}
return true;// All nodes return true without finding contradictions
}
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);// The initial color is -1
bool flag=true;
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
if(!dfs(i,1))// Dye the current dot into 1 Number color
{
flag=false;// Exit directly when there is an odd ring
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}
边栏推荐
- 2022-07-05 stonedb sub query processing parsing time analysis
- Classification, function and usage of MySQL constraints
- Designed for decision tree, the National University of Singapore and Tsinghua University jointly proposed a fast and safe federal learning system
- 动作捕捉用于蛇运动分析及蛇形机器人开发
- leetcode:面试题 17.24. 子矩阵最大累加和(待研究)
- UE4 blueprint learning chapter (IV) -- process control forloop and whileloop
- Aardio - Method of batch processing attributes and callback functions when encapsulating Libraries
- Leetcode: interview question 17.24 Maximum cumulative sum of submatrix (to be studied)
- Leetcode exercise - Sword finger offer 26 Substructure of tree
- NPM cannot install sharp
猜你喜欢
Signed and unsigned keywords
Cocoscreator+typescripts write an object pool by themselves
Improving Multimodal Accuracy Through Modality Pre-training and Attention
[leetcode] 19. Delete the penultimate node of the linked list
pytorch_ Yolox pruning [with code]
Unified Focal loss: Generalising Dice and cross entropy-based losses to handle class imbalanced medi
Sword finger offer question brushing record 1
MATLAB小技巧(27)灰色预测
MySQL ---- first acquaintance with MySQL
Aardio - integrate variable values into a string of text through variable names
随机推荐
Method of canceling automatic watermarking of uploaded pictures by CSDN
[compilation principle] LR (0) analyzer half done
2022-07-04 the high-performance database engine stonedb of MySQL is compiled and run in centos7.9
枚举与#define 宏的区别
npm无法安装sharp
树的先序中序后序遍历
2022-07-05 stonedb sub query processing parsing time analysis
【踩坑合辑】Attempting to deserialize object on CUDA device+buff/cache占用过高+pad_sequence
ACL 2022 | 序列标注的小样本NER:融合标签语义的双塔BERT模型
C# 三种方式实现Socket数据接收
Extern keyword
Designed for decision tree, the National University of Singapore and Tsinghua University jointly proposed a fast and safe federal learning system
Rust knowledge mind map XMIND
机试刷题1
Comparison between variable and "zero value"
Detailed explanation of ThreadLocal
The difference between enumeration and define macro
Windows Auzre 微软的云计算产品的后台操作界面
Sizeof keyword
Financial professionals must read book series 6: equity investment (based on the outline and framework of the CFA exam)