DSA Mastery理论与实验教程

外观

动手实验

Lab 07-E-26：BFS 二分图判定

用 BFS 黑白染色判定无向图是否为二分图，冲突时输出首次发现的冲突边。

07E2660～90 分钟更新于 2026-09-19Qing、Azen、qzm123基础draft

题目来源：改编自 LeetCode 785：判断二分图。原题接收邻接表并只返回布尔值；本 Lab 改用无向边集输入，并额外输出一组确定的染色或首次发现的冲突边。

学习目标 ​

前置知识 ​

完成前建议先阅读第 7.1 节 图的遍历：DFS 与 BFS的"BFS 能做什么"小节。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。

题目 ​

如果一个无向图的顶点能够被分成两个集合，并且每条边的两个端点分别属于不同集合，这个图就是二分图。请用 BFS 为顶点染成 0/1 两色：若成功，输出一组符合固定规则的染色；若发现相邻顶点同色，输出按固定遍历规则最先发现的冲突边。

输入格式 ​

第一行包含两个整数 n m，分别表示顶点数和无向边数。顶点编号为 0 到 n-1。

接下来 m 行，每行包含两个整数 u v，表示一条无向边。输入保证：

  • 1 <= n <= 100000；
  • 0 <= m <= 200000；
  • 0 <= u, v < n；
  • 不包含自环和重复边；
  • 图不保证连通。

为保证结果唯一，遍历规则固定为：

  1. 按编号从 0 到 n-1 依次扫描，对尚未染色的顶点作为 BFS 起点，起点染 0；
  2. 每个顶点的邻居按编号升序处理；
  3. 处理中发现第一条冲突边（两个端点颜色相同）时，立即终止整个程序并输出它。

输出格式 ​

输出两行，分两种情况：

二分图：第一行输出 YES，第二行输出 n 个整数 color[0] color[1] ... color[n-1]，取值 0 或 1。孤立顶点在各自起点染 0，直接输出 0。

非二分图：第一行输出 NO，第二行输出两个整数 u v，表示按上述规则首次发现的冲突边的两个端点，保证 u < v。

两行之间以换行分隔，行末无多余空格。

样例输入 ​

input
5 4
1 3
0 1
1 4
0 2

样例输出 ​

output
YES
0 1 1 0 0

任务 ​

  1. 读入无向图，构建邻接表并升序排序；
  2. 初始化 color 为 -1（未染色），从 0 号顶点开始扫描；
  3. 遇到未染色顶点时染 0 并入队，开始 BFS；
  4. 出队顶点 u，对每个邻居 v：未染色则染 1 - color[u] 并入队；已染色且与 color[u] 相同，则发现冲突边 (u, v)；
  5. 冲突时输出 NO 与该边（min(u, v) 在前），立即结束；全部处理完则输出 YES 与颜色数组。

输出唯一性

非连通图中可能有多个冲突边。本题按"根升序扫描 + 邻居升序 + 首次发现即终止"的规则保证输出唯一，标准答案据此生成。

正常、边界与错误情况 ​

情况预期行为
二分图（含树、偶环、星形）YES + 合法的 0/1 染色数组
奇环（如三角形）染色到某条边两端同色，输出 NO + 该边
非连通且冲突在后面的分量第一个冲突边以首次发现的为准
孤立顶点染 0，正常输出
单顶点图YES，颜色 0
单边图YES，两个端点异色

运行与评分 ​

在本 Lab 目录执行：

powershell
make doctor
make run
make run CASE=001-sample
make score

未安装 Make 时，在仓库根目录执行：

powershell
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-26-bfs-bipartite
pnpm lab:run -- labs/chapter-07/exercise/E-07-26-bfs-bipartite
pnpm lab:score -- labs/chapter-07/exercise/E-07-26-bfs-bipartite

完成清单 ​

解题思路 ​

对每个未染色顶点启动 BFS，并给相邻顶点染相反颜色。若发现一条边连接了同色顶点，图不是二分图；记录扫描顺序中的第一条冲突边即可满足确定性输出。

复杂度分析 ​

为了固定首次冲突边，排序全部邻接表需要 O(Σ deg(u) log deg(u)) 时间，上界可写为 O(m log n)。排序完成后，每个顶点最多入队一次，邻接表中的每条记录扫描一次，也就是每条无向边最多扫描两个方向，BFS 本身为 O(n + m)；因此包含排序的总时间为 O(n + m log n)。

颜色数组与队列各占 O(n) 空间，邻接表占 O(n + m) 空间。BFS 不使用递归，不受系统调用栈深度限制。

思考与复盘 ​

  1. 为什么二分图等价于“不含奇环”？发现一条同色冲突边后，如何结合两个端点在 BFS 树中的路径还原出奇环？
查看参考答案

沿边交替染色时，偶环可一致染色，奇环会迫使起点出现两种颜色。发现同色边后，沿 BFS 父指针回溯到最近公共祖先并拼接冲突边，可得到奇环。

  1. 如果把 BFS 换成 DFS 染色，判定结果会变吗？为什么？
查看参考答案

不会。二染色是否可行只取决于是否含奇环；遍历顺序可能改变颜色方案和首次冲突边，但不改变 YES/NO 结论。

  1. 若输出要求改为"任意一条冲突边"，评测会遇到什么问题？固定扫描规则解决了什么？
查看参考答案

同一图可能有多条合法冲突边，不同邻接顺序会产生不同文本输出。固定根顺序、邻居顺序和首次冲突终止后，标准答案唯一可复现。

  1. 二分图判定还能用哪些工具实现（如并查集奇偶性）？各自需要多记录什么信息？
查看参考答案

可用带奇偶势的并查集维护每个顶点到根的颜色异或值，合并边时检查异或约束；它适合动态加边，但不直接提供 BFS 层次或冲突路径。