当前位置:网站首页>Chromatic judgement bipartite graph
Chromatic judgement bipartite graph
2022-07-06 12:56:00 【Classmate Chen_】
One 、 What is a bipartite graph ( Bipartite graph )?
Definition : Bipartite graphs are also called bipartite graphs , It's a special model in graph theory . set up G=(V,E) It's an undirected graph , If the vertex V It can be divided into two disjoint subsets (A,B), And every edge in the graph (i,j) The two vertices associated i and j They belong to these two different vertex sets (i in A,j in B), It's called a picture G For a bipartite graph .
In other words : All points of a graph can be divided into two disjoint subsets , And the two points attached to each edge in the graph belong to these two disjoint subsets , The vertices in two subsets are not adjacent .
The following three graphs are bipartite graphs :
Two 、 How can we distinguish a bipartite graph ?
By definition , Distinguishing a bipartite graph is whether all points in the graph can be divided into two independent point sets .
To prove it , If a graph is a bipartite graph , Then there must not be an odd loop in the graph .
Because if there is a circuit in a graph and the length of this circuit is odd , Then the points in this circuit should also be odd . According to the previous definition , The two points attached to each edge belong to these two disjoint subsets , However, the number of points is odd , Therefore, it must not be divided into two disjoint subsets .
For example, the following figure is not a bipartite graph , We can find whether the dots in the box are white or red , Will make two points attached to an edge in a subset ( Same color ).
Here we use the coloring method to judge the bipartite graph ( Depth first search version )
subject
Given a n A little bit m Undirected graph of strip and edge , There may be double edges and self rings in the graph .
Please judge whether this graph is bipartite .
Input format
The first line contains two integers n and m.
Next m That's ok , Each line contains two integers u and v, Indication point u Sum point v There is an edge between .
Output format
If a given graph is a bipartite graph , The output Yes
, Otherwise output No
.
Data range
1≤n,m≤10^5
sample input :
4 4
1 3
1 4
2 3
2 4
sample output :
Yes
This is a very basic introductory question , The title is to give us a picture , Let's judge whether it is a bipartite graph .
Ideas :
- Dyeing can use
1
and2
Distinguish between different colors , use0
Indicates not stained . - Traverse all points , Each time, the undyed points are searched for depth first , Default dyeing
1
perhaps2
- Here, if we cannot judge whether a certain point is dyed successfully, it means that the graph is a bipartite graph , To judge whether a certain point fails to stain ; Coloring failure is not a bipartite graph , Otherwise, it is a bipartite graph .
AC Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10,M=2*1e5+10; // Undirected graph , Number of edges *2
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b){
// Adjacency list
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u,int c){
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!color[j]){
if(!dfs(j,3-c)) return false; // If at present j Nodes are not stained , Will judge j Will there be contradictions when nodes are dyed with another color , In case of contradiction, return false( Is not a bipartite graph )
}
else if(color[j]==c) return false; // If the adjacent nodes have the same color , It's not a bipartite graph
}
return true; // If there is no dyeing failure, it will succeed
}
int main(){
int a,b;
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&a,&b);
add(a,b); // Undirected graph
add(b,a);
}
bool flag=true;
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,1)){
flag=false;
break;
}
}
}
if(flag)puts("Yes");
else puts("No");
return 0;
}
边栏推荐
- isEmpty 和 isBlank 的用法区别
- 【干货】提升RTK模糊度固定率的建议之周跳探测
- 基本Dos命令
- Naive Bayesian theory derivation
- The port is occupied because the service is not shut down normally
- Matlab读取GNSS 观测值o文件代码示例
- 记录:下一不小心写了个递归
- Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
- Itext 7 生成PDF总结
- Containers and Devops: container based Devops delivery pipeline
猜你喜欢
[算法] 剑指offer2 golang 面试题4:只出现一次的数字
Matlab读取GNSS 观测值o文件代码示例
idea问题记录
Problems and solutions of robust estimation in rtklib single point location spp
FairyGUI循环列表
FairyGUI条子家族(滚动条,滑动条,进度条)
Unity3d, Alibaba cloud server, platform configuration
染色法判定二分图
[algorithm] sword finger offer2 golang interview question 2: binary addition
[GNSS data processing] Helmert variance component estimation analysis and code implementation
随机推荐
WSL common commands
错误:排序与角标越界
Naive Bayesian theory derivation
Liste des boucles de l'interface graphique de défaillance
Basic DOS commands
Game 280 weekly
It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
(课设第一套)1-4 消息传递接口 (100 分)(模拟:线程)
[algorithm] sword finger offer2 golang interview question 1: integer division
[Chongqing Guangdong education] Shandong University College Physics reference materials
音乐播放(Toggle && PlayerPrefs)
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
Implementation of Excel import and export functions
FairyGUI按钮动效的混用
Fairygui gain buff value change display
GNSS定位精度指标计算
基本Dos命令
Unity scene jump and exit
The port is occupied because the service is not shut down normally
(课设第一套)1-5 317号子任务 (100 分)(Dijkstra:重边自环)