二分图检测（BFS/DFS）

题目描述
给定一个无向图，判断它是否是一个二分图。二分图是指能够将图中的所有顶点划分为两个不相交的集合，使得同一集合内的顶点之间没有边相连。换句话说，图中每条边的两个顶点必须属于不同的集合。如果图是二分图，返回划分方案；否则返回无法划分。

关键概念

• 二分图：顶点集可划分为两个独立集（内部无边）。
• 染色法：通过给顶点染色（如0和1）模拟划分，相邻顶点颜色需不同。

解题步骤

1. 初始化

   • 创建颜色数组color[]，初始值为-1（表示未染色）。
   • 遍历所有顶点，若遇到未染色的顶点，则从该顶点开始检测。

2. BFS/DFS遍历染色

   • 将当前顶点染成颜色0，其邻居染成颜色1，依次类推。
   • 遍历过程中若发现相邻顶点颜色相同，则不是二分图。

3. 检测冲突

   • 对于每条边(u, v)，检查color[u]和color[v]是否相等。若相等，立即返回失败。

4. 输出结果

   • 若全程无冲突，则根据颜色数组输出两个顶点集合。

详细过程
假设图用邻接表表示，以BFS为例：

1. 遍历每个顶点，若顶点i未染色，将其加入队列，染成0。
2. 当队列非空时，取出顶点u，遍历其邻居v：
   • 若v未染色，将其染成与u相反的颜色（1-color[u]），并加入队列。
   • 若v已染色且颜色与u相同，返回false。
3. 若所有顶点处理完毕且无冲突，返回true及颜色划分。

示例
图：顶点0-1-2，边为(0,1)、(1,2)。

• 从0开始染色：0→颜色0，邻居1→颜色1。
• 接着处理1：邻居2未染色，染成颜色0。
• 检查边(1,2)：颜色1和0不同，无冲突。
• 最终集合：{0,2}（颜色0）和{1}（颜色1）。

复杂度分析

• 时间：O(V+E)（每个顶点和边仅处理一次）。
• 空间：O(V)（存储颜色和队列）。

关键点

• 二分图等价于图中无奇环（长度为奇数的环）。
• 连通图只需一次BFS/DFS，非连通图需多次遍历。