首页 > 其他分享 >二分图的判定-染色法

二分图的判定-染色法

时间:2024-10-08 23:20:59浏览次数:13  
标签:二分 颜色 int 染色 color 判定 染色法 节点

二分图

如果一张无向图的N个节点可以分成A.B两个不相交的非空集合,并且同一集合内的点之间没有边相连,那么称该无向图为二分图(BipartiteGraph)。
定理:二分图不存在奇环(长度为奇数的环)。
因为每一条边都是从一个集合走到另一个集合,只有走偶数次才可能回到同一个集合。
在这里插入图片描述

染色法

我们可以使用染色法来判定二分图。即尝试用两种颜色标记图中的节点.当一个点被标记后,所有与它相邻的节点应该标记与它相反的颜色,若标记过程产生冲突,则说明图中存在奇环。可以用DFS或BFS来实现。

算法流程

1.color[]初始化为0,被访问的点的颜色是1或-1。
2.进入u,对u点染色。
3.枚举u的邻点V,

(1)若v未访问,走进去,若返回有奇环,则一路返回有奇环。
(2)若v已访问且v的颜色与u的颜色相同,则返回有奇环。

4.枚举完u的邻点,没有发现奇环,则返回没有奇环。

代码如下:

#include<iostream> 
using namespace std;

const int N = 5005; // 最大节点数
const int M = 5005; // 最大边数

int n, m; // 节点数和边数

struct edge
{
	int v, ne; // 目标节点和下一条边的索引
} e[M]; // 边数组

int h[N], idx; // 邻接表头指针数组和边数组索引
int color[N]; // 节点颜色数组

// 添加一条从节点 a 到节点 b 的无向边
void add(int a, int b)
{
	e[++idx] = { b, h[a] }; // 将节点 b 插入节点 a 的邻接表头部
	h[a] = idx; // 更新节点 a 的邻接表头指针
}

// 深度优先搜索判断是否存在二分图,并进行节点染色
bool dfs(int u, int c)
{
	color[u] = c; // 将当前节点染色为 c
	for (int i = h[u]; i; i = e[i].ne) // 遍历以节点 u 为起点的所有边
	{
		int v = e[i].v; // 取得当前边的目标节点 v
		if (!color[v]) // 如果节点 v 还未被染色
		{
			if (dfs(v, -c)) // 递归调用 dfs 染色节点 v,颜色为 -c
			{
				return true; // 如果存在冲突,返回 true
			}
		}
		else if (color[v] == c) // 如果节点 v 已经染色且颜色与当前节点相同
		{
			return true; // 存在冲突,返回 true
		}
	}
	return false; // 没有冲突,返回 false
}

int main()
{
	cin >> n >> m; // 输入节点数和边数
	for (int i = 0; i < m; i++) // 循环读入每条边的信息
	{
		int a, b;
		cin >> a >> b; // 输入边的两个节点
		add(a, b); // 添加无向边 a->b 和 b->a
		add(b, a);
	}
	bool flag = false; // 是否存在二分图的标志
	for (int i = 1; i <= n; i++) // 遍历所有节点
	{
		if (!color[i]) // 如果节点 i 还未染色
		{
			if (dfs(i, 1)) // 对节点 i 进行染色,从第一种颜色开始
			{
				flag = true; // 如果存在冲突,设置标志为 true
				break;
			}
		}
	}
	if (flag) // 如果存在冲突,输出 NO
	{
		cout << "NO" << endl;
	}
	else // 如果不存在冲突,输出 YES
	{
		cout << "YES" << endl;
	}

	return 0; // 程序正常结束
}

使用vector容器和queue队列

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100005; // 最大节点数
vector<int> adj[N]; // 邻接表
int color[N]; // 节点颜色数组

bool isBipartite(int n) {
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (color[i] == 0) { // 如果节点未被染色
			q.push(i); // 将当前节点入队
			color[i] = 1; // 染色为第一种颜色
			while (!q.empty()) {
				int u = q.front();
				q.pop();
				for (int v : adj[u]) {
					if (color[v] == 0) { // 如果相邻节点未被染色
						color[v] = -color[u]; // 染成与当前节点不同的颜色
						q.push(v); // 将相邻节点入队
					}
					else if (color[v] == color[u]) { // 如果相邻节点与当前节点颜色相同
						return false; // 不是二分图
					}
				}
			}
		}
	}
	return true; // 所有连通分量都是二分图
}

int main() {
	int n, m; // 节点数和边数
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u); // 无向图,需要双向连接
	}

	fill(color, color + n + 1, 0); // 初始化节点颜色数组

	if (isBipartite(n)) {
		cout << "YES" << endl; // 是二分图
	}
	else {
		cout << "NO" << endl; // 不是二分图
	}

	return 0;
}

标签:二分,颜色,int,染色,color,判定,染色法,节点
From: https://blog.csdn.net/buaichifanqie/article/details/142770937

相关文章

  • NOIP2024集训Day47 生成树+二分图
    NOIP2024集训Day47生成树+二分图B.[THUPC2022初赛]最小公倍树直接建边显然不行,考虑优化建边。对于两个点\(u,v\),\((u,v)\)的边权为\(\displaystyle\operatorname{lcm}(u,v)=\frac{u\timesv}{\gcd(u,v)}\),显然应该选择\(\gcd(u,v)\)尽可能大的点对连边,也就是......
  • Codeforces Round 316 (Div. 2) D题 Tree Requests(二分,dfs,在线,前缀异或)
    题目链接CodeforcesRound316(Div.2)D题TreeRequests思路将262626个字母全部当作一个二进制数。将每个深度的结点按照dfs序放到一个vector里,同时记录每个vector......
  • 【前缀和+开区间二分】codeforces 1187 B. Letters Shop
    题意第一行,输入一个正整数\(n(1\leqn\leq2*10^5)\),代表字符串\(s\)的长度。第二行,输入一个字符串\(s\)。第三行,输入一个正整数\(m(1\leqm\leq5*10^4)\),代表接下来要输入的询问次数,对于每次询问:输入一个字符串\(t(1\leq|t|\leq2*10^5)\),并保证\(\sum_{i=1}^m......
  • 【二分】【边界判定】
    https://ac.nowcoder.com/acm/contest/22353/G注意点:check中,不仅要判断用的joker数是否大于joker牌的数量,还要判断组成套数是否小于用的joker数量,原文链接:https://blog.csdn.net/a_forever_dream/article/details/106548941#include<bits/stdc++.h>typedeflonglongll;usi......
  • [Python手撕]判断二分图
    classSolution:defisBipartite(self,graph:List[List[int]])->bool:defbfs(i):color[i]=1queue=[(i,1)]whilequeue:t,c=queue.pop(0)nc=0......
  • 【二分】华华给月月准备礼物
    https://ac.nowcoder.com/acm/contest/22353/F注意点是count+=length/mid,在题目中,count+=length/mid的含义是计算每根木棍可以被裁剪成多少段长度为mid的木棍。这里的整除是指length/mid,它计算的是在给定的木棍长度length中,最多可以切出多少段长度为mid的完整......
  • 【贪心】【二分】[NOIP2015]跳石头
    https://ac.nowcoder.com/acm/contest/22353/C正确的思路是二分查找+贪心。具体来说,可以通过二分来猜测一个最小的跳跃距离,然后通过贪心算法判断是否可以通过移除石头使所有的跳跃都满足这个最小跳跃距离。这种方法的核心是逐步逼近最优解,而不是直接删除前m小的元素。细节:在......
  • 代码随想录算法训练营day7|704.二分查找、27.移除元素、977.有序数组的平方
    学习资料:https://programmercarl.com/数组理论基础.html理解:双指针可以同时获取一个数组的两个位置的值二分查找:根据区间范围(左闭右闭、左闭右开)来判断左右指针比较方式刷题记录:704.二分查找(左闭右闭则<=,左右指针,middle=left+(right-left)//2,因为考虑了等号情况所以下一步l......
  • Codeforces Round 973 (Div. 2) - D题二分
    首先这道题的一个坑点就是求max(a[1],a[2],...,a[n])和求min(a[1],a[2],...,a[n])是完全独立的,不会相互影响(可能是我读题能力太差,一直卡在这点了。。。)这道题二分是一种很好想的方法,题中提到max和min,我们就可以想到只要让最大值最小,让最小值最大就可以达到我的目的了,二分的......
  • 【有啥问啥】二分图(Bipartite Graph)算法原理详解
    二分图(BipartiteGraph)算法原理详解引言二分图(BipartiteGraph),又称二部图,是图论中的一个重要概念。在实际应用中,二分图模型经常用于解决如匹配问题、覆盖问题和独立集问题等。本文将详细解析二分图的基本概念、性质、判定方法,以及求解最大匹配问题的匈牙利算法,并探讨其在......