二分图
如果一张无向图的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