题目来源：改编自 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；- 不包含自环和重复边；
- 图不保证连通。
为保证结果唯一，遍历规则固定为：
- 按编号从
0到n-1依次扫描，对尚未染色的顶点作为 BFS 起点，起点染0； - 每个顶点的邻居按编号升序处理；
- 处理中发现第一条冲突边（两个端点颜色相同）时，立即终止整个程序并输出它。
输出格式
输出两行，分两种情况：
二分图：第一行输出 YES，第二行输出 n 个整数 color[0] color[1] ... color[n-1]，取值 0 或 1。孤立顶点在各自起点染 0，直接输出 0。
非二分图：第一行输出 NO，第二行输出两个整数 u v，表示按上述规则首次发现的冲突边的两个端点，保证 u < v。
两行之间以换行分隔，行末无多余空格。
样例输入
5 4
1 3
0 1
1 4
0 2样例输出
YES
0 1 1 0 0任务
- 读入无向图，构建邻接表并升序排序；
- 初始化
color为-1（未染色），从0号顶点开始扫描； - 遇到未染色顶点时染
0并入队，开始 BFS； - 出队顶点
u，对每个邻居v：未染色则染1 - color[u]并入队；已染色且与color[u]相同，则发现冲突边(u, v)； - 冲突时输出
NO与该边（min(u, v)在前），立即结束；全部处理完则输出YES与颜色数组。
输出唯一性
非连通图中可能有多个冲突边。本题按"根升序扫描 + 邻居升序 + 首次发现即终止"的规则保证输出唯一，标准答案据此生成。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 二分图（含树、偶环、星形） | YES + 合法的 0/1 染色数组 |
| 奇环（如三角形） | 染色到某条边两端同色，输出 NO + 该边 |
| 非连通且冲突在后面的分量 | 第一个冲突边以首次发现的为准 |
| 孤立顶点 | 染 0，正常输出 |
| 单顶点图 | YES，颜色 0 |
| 单边图 | YES，两个端点异色 |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-06-bfs-bipartite
pnpm lab:run -- labs/chapter-07/exercise/E-07-06-bfs-bipartite
pnpm lab:score -- labs/chapter-07/exercise/E-07-06-bfs-bipartite完成清单
复杂度分析
为了固定首次冲突边，排序全部邻接表需要 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 不使用递归，不受系统调用栈深度限制。
思考与复盘
- 为什么二分图等价于“不含奇环”？发现一条同色冲突边后，如何结合两个端点在 BFS 树中的路径还原出奇环？
查看参考答案
沿边交替染色时，偶环可一致染色，奇环会迫使起点出现两种颜色。发现同色边后，沿 BFS 父指针回溯到最近公共祖先并拼接冲突边，可得到奇环。
- 如果把 BFS 换成 DFS 染色，判定结果会变吗？为什么？
查看参考答案
不会。二染色是否可行只取决于是否含奇环；遍历顺序可能改变颜色方案和首次冲突边，但不改变 YES/NO 结论。
- 若输出要求改为"任意一条冲突边"，评测会遇到什么问题？固定扫描规则解决了什么？
查看参考答案
同一图可能有多条合法冲突边，不同邻接顺序会产生不同文本输出。固定根顺序、邻居顺序和首次冲突终止后，标准答案唯一可复现。
- 二分图判定还能用哪些工具实现（如并查集奇偶性）？各自需要多记录什么信息？
查看参考答案
可用带奇偶势的并查集维护每个顶点到根的颜色异或值，合并边时检查异或约束；它适合动态加边，但不直接提供 BFS 层次或冲突路径。