网站模块是什么,基于cms系统网站的建设,asp网站开发程序员,个人可以备案企业网站吗文章目录 题目描述二分图介绍和基本思路实现代码#xff08;C#xff09; 题目描述
给定一个n个点m条边的无向图#xff0c;图中可能存在重边和自环。请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。接下来m行#xff0c;每行包含两个整数u和v#xf… 文章目录 题目描述二分图介绍和基本思路实现代码C 题目描述
给定一个n个点m条边的无向图图中可能存在重边和自环。请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。接下来m行每行包含两个整数u和v表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图则输出Yes否则输出No。
数据范围
1 ≤ n,m ≤ 10^5
二分图介绍和基本思路
二分图的定义一种特殊的无向图其顶点集可以划分为两个不相交的子集使得每一条边都恰好连接两个子集中的顶点即每一条边都是跨集合的。二分图判定定理一个图是二分图当且仅当图中不含有边数为奇数的环。染色法判定二分图的思想在深度优先搜索DFS的过程中对图中的顶点进行染色如果染色的过程中任何两个相邻的顶点被染成了相同的颜色则这个图就不是二分图否则该图就是二分图。
实现代码C
#include cstdio
#include vector
using namespace std;// 【辅助常量定义】无向图中的点个数上限
const int N 100010;// 【变量定义】无向图中点的个数和边的条数
int n, m;
// 【变量定义】无向边的两个端点的编号
int u, v;
// 【变量定义】用于存储无向边信息的邻接表
vectorint edges[N];
// 【变量定义】用于记录二分图判定的结果
bool result;
// 【变量定义】用于记录哪些点被染色了初始所有元素都为0表示所有点都未被染色
int colored[N];// 【函数定义】用于给无向图中指定编号的点和与其可以连接的点进行染色的函数
bool coloring(int number, int color)
{// 【判定阶段】如果该点没有进行染色则对其以及与其相连的点进行染色if(colored[number] 0) {// 首先对该点进行染色colored[number] color;// 对与该点相连的顶点进行染色当前顶点是颜色1则染颜色2否则染颜色1for(int node : edges[number]) {if(coloring(node, 3 - color) false) return false;}// 判定可以染色return true;}// 如果该点已经完成了染色则判定其染色结果与本次待染的颜色是否矛盾如果矛盾则返回falseelse{if(colored[number] ! color) return false;}
}// 【函数定义】用于判定一张无向图是否是二分图的函数
bool judge_graph(void)
{// 【点的遍历】顺序遍历无向图中的每一个点并对该点所有连接的点进行染色染第一种颜色for(int i 1; i n; i){// 【判定阶段】如果当前点还没有进行染色则对该点以及与该点连接的点进行染色// 如果染色过程中发生矛盾则输出结果if(colored[i] 0) if(coloring(i, 1) false) return false;}// 如果成功完成了对无向图中所有点的染色则说明该图是二分图return true;
}int main(void)
{// 【变量输入】输入无向图中点的个数和边的条数scanf(%d%d, n, m);// 【变量输入】输入无向图中的每一条边for(int i 0; i m; i){scanf(%d%d, u, v);// 使用邻接表来存储无向边的信息edges[u].push_back(v);edges[v].push_back(u);}// 【获取结果】使用自定义的函数判定该无向图是否是二分图result judge_graph();// 【结果输出】根据结果输出该无向图是否是二分图if(result true) printf(Yes);else printf(No);return 0;
}
