二分图
如果一张无向图的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; // 将当前节点染色为 cfor (int i = h[u]; i; i = e[i].ne) // 遍历以节点 u 为起点的所有边{int v = e[i].v; // 取得当前边的目标节点 vif (!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->aadd(b, a);}bool flag = false; // 是否存在二分图的标志for (int i = 1; i <= n; i++) // 遍历所有节点{if (!color[i]) // 如果节点 i 还未染色{if (dfs(i, 1)) // 对节点 i 进行染色，从第一种颜色开始{flag = true; // 如果存在冲突，设置标志为 truebreak;}}}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;
}
