当前位置:网站首页>染色法判定二分图
染色法判定二分图
2022-07-06 09:18:00 【小陈同学_】
一、什么是二分图(二部图)?
定义:二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
换句人话来说:一个图的所有点可以划分为两个互不相交子集,并且图中每条边依附的两个点都分别属于这两个互不相交的子集,两个子集内的顶点不相邻。
下面这三个图就是二分图:
二、我们如何来辨别二分图呢?
根据定义来看,辨别二分图就是能否把图中的所有点分成两个独立的点集。
证明来看,如果一个图是二分图,那么该图必然不存在一个回路的长度为奇数。
因为一个图中如果存在一个回路并且这个回路的长度为奇数的话,那么这个回路中的点也应该为奇数。根据前面定义,每条边依附的两个点都分别属于这两个互不相交的子集,然而点数为奇数,所以肯定不可以划分成两个互不相交的子集。
比如下图就不是一个二分图,我们可以发现无论方框中的点为白色还是红色,都会让一条边依附的两个点在一个子集(颜色相同)。
这里我们利用染色法来判断二分图(深度优先搜索版本)
题目
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 u 和 v,表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图,则输出 Yes
,否则输出 No
。
数据范围
1≤n,m≤10^5
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
这是一个非常基础的入门题,题目就是给我们一个图,让我们判断是否为二分图。
思路:
- 染色可以使用
1
和2
区分不同颜色,用0
表示未染色。 - 遍历所有点,每次将未染色的点进行深度优先搜索, 默认染成
1
或者2
- 在这里我们不能判断某个点染色成功则说明该图是二分图,要判断某个点是否染色失败;染色失败则不是二分图,否则为二分图。
AC代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10,M=2*1e5+10; //无向图,边数*2
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b){
//邻接表
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; //如果当前j节点没有染色,就判断j节点染另一个颜色会不会出现矛盾,出现矛盾返回false(则不是二分图)
}
else if(color[j]==c) return false; //如果相邻的节点颜色相同,就不是二分图
}
return true; //如果没有染色失败则成功
}
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); //无向图
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;
}
边栏推荐
- Guided package method in idea
- FairyGUI人物状态弹窗
- Expected value (EV)
- Get the position of the nth occurrence of the string
- [算法] 剑指offer2 golang 面试题4:只出现一次的数字
- FairyGUI简单背包的制作
- The master of double non planning left the real estate company and became a programmer with an annual salary of 25W. There are too many life choices at the age of 25
- FairyGUI摇杆
- 平衡二叉树详解 通俗易懂
- 【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
猜你喜欢
Mysql database index
Unity3D制作注册登录界面,并实现场景跳转
Unity scene jump and exit
idea中导包方法
Unity3d makes the registration login interface and realizes the scene jump
First use of dosbox
FairyGUI简单背包的制作
(5) Introduction to R language bioinformatics -- ORF and sequence analysis
Guided package method in idea
Excel导入,导出功能实现
随机推荐
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
GNSS定位精度指标计算
[leetcode19]删除链表中倒数第n个结点
It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
Vulnhub target: hacknos_ PLAYER V1.1
FairyGUI簡單背包的制作
FairyGUI循环列表
There is no red exclamation mark after SVN update
[offer29] sorted circular linked list
Fairygui gain buff value change display
What are the functions and features of helm or terrain
[Chongqing Guangdong education] Shandong University College Physics reference materials
FairyGUI条子家族(滚动条,滑动条,进度条)
[offer18] delete the node of the linked list
【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
Esp8266 connect onenet (old mqtt mode)
First use of dosbox
[算法] 剑指offer2 golang 面试题6:排序数组中的两个数字之和
C programming exercise
[leetcode622] design circular queue