【题目来源】
AcWing：860. 染色法判定二分图 - AcWing题库
【题目描述】
给定一个 \(n\) 个点 \(m\) 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
【输入】
第一行包含两个整数 \(n\) 和 \(m\)。
接下来 \(m\) 行，每行包含两个整数 \(u\) 和 \(v\)，表示点 \(u\) 和点 \(v\) 之间存在一条边。
【输出】
如果给定图是二分图，则输出 Yes，否则输出 No。
【输入样例】
4 4
1 3
1 4
2 3
2 4
【输出样例】
Yes
【算法标签】
《AcWing 860 染色法判定二分图》 #二分图判定# #染色法#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间const int N = 100010; // 定义常量：最大节点数
int n, m; // 定义变量：节点数n，边数m
vector<int> G[N]; // 定义邻接表：存储图的边关系
int color[N]; // 定义数组：存储节点的颜色（0未染色，1红色，-1黑色）
bool flag; // 定义标志：是否为二分图/*** 深度优先搜索进行二分图染色* @param x 当前处理的节点*/
void dfs(int x)
{// 遍历当前节点的所有邻接节点for (int i = 0; i < G[x].size(); i++) {int y = G[x][i]; // 获取邻接节点编号// 如果当前节点与邻接节点颜色相同，不是二分图if (color[x] == color[y]) {flag = false;return;}// 如果邻接节点未染色，则染相反颜色if (color[y] == 0) {color[y] = -color[x]; // -1表示黑色dfs(y); // 递归处理邻接节点}}
}int main()
{cin >> n >> m; // 输入节点数和边数// 构建图的邻接表（无向图）for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v; // 输入边的关系G[v].push_back(u); // 添加双向边G[u].push_back(v);}flag = true; // 初始化标志为真// 对每个未染色的节点进行染色for (int i = 1; i <= n; i++) {if (color[i] == 0) // 如果节点未染色{color[i] = 1; // 染成红色（1）dfs(i); // 开始深度优先搜索}}// 输出判断结果if (flag == true) cout << "Yes"; // 是二分图else cout << "No"; // 不是二分图return 0; // 程序正常结束
}
//再写一遍
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间const int N = 100005, M = 200005; // 定义常量：N为最大节点数，M为最大边数
vector<int> h[N]; // 定义邻接表：h[i]存储节点i的所有邻接节点
int n, m; // 定义变量：节点数n，边数m
int color[N]; // 定义数组：color[i]表示节点i的颜色（0未染色，1或2表示两种颜色）/*** 深度优先搜索进行二分图染色* @param u 当前处理的节点* @param c 当前节点要染的颜色（1或2）* @return 染色是否成功（是否是二分图）*/
bool dfs(int u, int c)
{color[u] = c; // 将当前节点染成c色// 遍历当前节点的所有邻接节点for (int i = 0; i < h[u].size(); i++) {int j = h[u][i]; // 获取邻接节点编号if (color[j] == 0) // 如果邻接节点未染色{// 递归尝试将邻接节点染成另一种颜色（3-c）if (dfs(j, 3 - c) == false) return false;} else if (color[j] == c) // 如果邻接节点颜色与当前节点相同{return false; // 染色失败，不是二分图}}return true; // 染色成功
}int main()
{cin >> n >> m; // 输入节点数和边数// 构建图的邻接表（无向图）while (m--) {int a, b;cin >> a >> b; // 输入边的关系h[a].push_back(b); // 添加双向边h[b].push_back(a);}bool flag = true; // 初始化标志为真// 对每个未染色的节点进行染色for (int i = 1; i <= n; i++) {if (color[i] == 0) // 如果节点未染色{// 尝试将节点i染成颜色1，如果失败则不是二分图if (dfs(i, 1) == false) {flag = false;break;}}}// 输出判断结果if (flag) cout << "Yes" << endl; // 是二分图else cout << "No" << endl; // 不是二分图return 0; // 程序正常结束
}
【运行结果】
4 4
1 3
1 4
2 3
2 4
Yes