染色法判定二分图的核心逻辑是利用“二分图等价于无奇数长度环”的性质，用两种颜色对顶点染色，要求每条边两端颜色不同；若染色中出现相邻顶点同色则非二分图，且需对每个未访问连通分量单独启动染色。
染色法判定二分图的核心逻辑是什么
二分图等价于「无奇数长度环」，而染色法正是利用这个性质：尝试用两种颜色（比如 0 和 1）给所有顶点着色，要求每条边的两个端点颜色不同。只要染色过程中没出现矛盾，图就是二分图。
关键判断点：一旦发现某条边 (u, v) 的两端已被染成相同颜色，立刻返回 false。注意：图不连通时需对每个未访问连通分量单独启动染色。
BFS 实现时如何避免重复入队和漏染
BFS 更直观地体现“逐层扩散”特性，适合初学理解；但容易在实现中忽略两个常见问题：一是未在入队前检查邻点是否已染色，导致重复入队甚至死循环；二是对孤立点或新连通分量忘记初始化颜色。
实操建议：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 用
vector<int> color(n, -1)</int>初始化，-1 表示未访问/未染色 - 对每个
i从 0 到n-1，若color[i] == -1，则设color[i] = 0并启动 BFS - 入队前先检查邻点：
if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }，否则立即判断if (color[v] == color[u]) return false
DFS 实现要注意递归栈与颜色传递方式
DFS 写起来更紧凑，但容易错在：把颜色值作为全局变量而非参数传递，导致跨连通分量污染；或在递归返回后没及时终止整个判定流程。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 写成带返回值的递归函数：
bool dfs(int u, int c, const vector<vector>>& graph, vector<int>& color)</int></vector> - 入口处先设
color[u] = c，再遍历所有邻点v：
– 若color[v] == -1，递归调用dfs(v, 1 - c, ...)并检查返回值
– 若color[v] == c，直接 return false - 主循环中每次调用
dfs(i, 0, ...)后必须检查返回值，任一 false 就整体返回 false
邻接表构建和图类型细节影响结果吗
不影响算法正确性，但影响代码健壮性。常见疏忽包括：输入是无向图却只存单向边、节点编号从 1 开始却按 0 索引访问数组、graph 大小未初始化为 n 导致越界。
典型错误现象：vector out of range 或漏判某个连通块。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 建图时对每条边
u-v，务必执行graph[u].push_back(v)和graph[v].push_back(u) - 确认输入节点范围：若题目说「1 ≤ u, v ≤ n」，则
vector<vector>> graph(n + 1)</vector>，且遍历从 1 到 n - 若用
vector<vector>> graph(n)</vector>，则所有输入节点需先减 1
真正容易被忽略的是：多个连通分量中某一个染色失败，其他分量仍会继续跑——必须在每轮染色后检查返回结果，不能只依赖最后一次调用。
