染色法判断二分图
admin
2024-02-12 02:53:20
0次

二分图：

二分图又称作二部图，指的是图中的点可以分割成两个点集，每个点集中的点之间没有边将他们相连。一个图是二分图，那么他必然不含奇数环。

染色法：

先随意取出一个未染色的点，然后对其染色，把其相邻的点染上其他颜色（二染色），如果所有点都染完也不存在冲突的话，那么就是二分图。

染色的过程就是遍历所有点的过程，所以深搜和宽搜都可以。

二染色技巧：1代表一种颜色,2代表一种颜色，每次用3减去当前颜色就是另一种颜色了。

注意：

1.二分图是无向图，一个边要在邻接矩阵中存储两次。

2.二分图不一定是联通的，分成多个二分集合也是可以的。

输入格式：
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式：

如果给定图是二分图，则输出Yes，否则输出No。

深搜代码：

#include
#include
using namespace std;const int N = 1e6 + 10;
int e[N], ne[N], h[N], idx = 0;
int color[N];
int n, m;void add(int a, int b) {ne[idx] = h[a], e[idx] = b, h[a] = idx++;
}bool dfs(int a, int b) {color[a] = b;for (int i = h[a]; i != -1; i = ne[i]) {if (!color[e[i]]) {if (!dfs(e[i], 3 - b))return false;}else if (color[e[i]] == b)return false;}return true;
}int main() {memset(h, -1, sizeof h);cin >> n >> m;int a, b;while (m--) {cin >> a >> b;add(a, b), add(b, a);}bool flag = true;for (int i = 1; i <= n; i++) {if (!color[i]) {//如果没染色color[i] = 1;if (!dfs(i, 1)){flag = false;break;}}}if (flag)cout << "Yes";else cout << "No";return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：excel导入导出demo笔记

下一篇：大年初二迎旅游热潮：西安“赢麻了”，廉航机票价格翻倍 澶у勾鍒濅簩杩庢梾娓哥儹娼タ瀹夎耽楹讳簡 澶у勾鍒濅簩鍘昏タ瀹夌殑绁ㄨ繕鑳芥姠鍒板悧

相关内容

热门资讯

酒香浸润烟火处：亿星酒业连锁门... 当清晨的阳光洒满社区的林荫道，当傍晚的大排档升腾起诱人香气，当路边的晚风拂去行人的疲惫，亿星名酒连锁...
喜稻拌饭——温暖偕行 喜稻拌饭起源于山西省，扎根于传统朝鲜族拌饭的深厚底蕴，将朝鲜族料理中对食材新鲜度的严苛把控、酱料调配...
就这个菜下酒下饭
经典名肴——红烧鸡块 编者按：本公众号自2016年创立以来，一直关注人类科学（史）、技术（史）、博物（史）三大领域。当下，...
衣食住行跟我逛︱小时候的味道！... 作为苏州人从小吃到大的美食，除了苏式汤面和生煎馒头，还有甜咸适口的粢饭团。近日，记者了解到，位于苏州...
中伏将至，头伏饺子二伏面，5道... 7月30日即将迎来中伏，老话说：“头伏饺子二伏面”，中伏，天气异常炎热，人体新陈代谢加快，对能量的需...
姑苏早点来丨月泊湾，重温“小辰... 月泊湾·壹号菜市场 前身为三香农贸市场 去年底完成改造焕新 熟悉的烟火气依旧氤氲升腾 📍月泊湾·壹...
原创 唤... 晨光中的谷物交响曲 六点三十分，闹钟在朦胧中响起。厨房里飘来咖啡的香气，阳光透过纱帘在地板上投下斑...
【技术流】揭秘四川豆瓣民间工艺...
强烈推荐这个泡萝卜配方，真是太...
【有一种叫云南的生活】气候凉爽... 入夏以来，秋城昭阳迎来了大批避暑旅居的川渝游客。他们在昭阳的各大公园里欢歌起舞，畅享清凉夏日带来的惬...
2025年火把节全州接待游客8... 激情火把节，最炫民族风。 7月18日晚，2025年凉山彝族火把节开幕式在西昌举行，凉山再次进入一年一...
博物馆奇妙夜：五家大湾区博物馆... 暑假，博物馆又成了热门打卡点，广东省博物馆的预约门票更是一票难求。旅游平台数据显示，7月中上旬，博物...
阜新市十佳研学旅游示范基地“出... 经阜新市文旅广电局、阜新市教育局、阜新市团市委、阜新市传媒中心及旅游协会组成的专家组严格评审并公示，...
西藏之旅第一站雅安自驾游大本营... 西藏之旅第一站雅安自驾游大本营 从这里正式挑战318房车旅行生活 自驾游
原创 泰... 泰国和柬埔寨，哪个实力更强？不用想就知道泰国吊打柬埔寨。但问题的关键是，他们可能打起来，但是大打特打...
环游的脚步没挡住，前列腺增生的... 退休后我和老伴计划环游全国，可第一站就出了岔子。在杭州西湖边，才走了半小时，我就觉得不对劲，赶紧找了...
新华视点｜暑期经济“热”力全开... 这个暑期，全国文旅市场迎来消费热潮，各地依托特色资源打造沉浸式体验，点燃夏日经济新引擎。 河南开封：...
【爱我英雄城 见我文明行】西湖... 为进一步提升旅游景区的文明形象， 优化游客旅游体验， 近期西湖区通过实地排查、 精准整改、强化引导等...
新疆大环线10日游定制团价格多... 七月的新疆，简直是上帝打翻的调色盘！雪山、草原、湖泊、沙漠在阳光下绽放着最浓烈的色彩，走一趟新疆大环...