6.3 综合题：判断二分图

二分图可用BFS染色：每个未染色分量任选颜色0；沿边给邻居染相反颜色。若发现相邻同色则不是二分图。DFS同样可做。

手工状态

三角形0-1-2-0：0染0，1和2染1；处理1看到2同为1，冲突。四环则可交替0,1,0,1，无冲突。

结构与代码

for(s)if(color[s]<0){color[s]=0;q.push(s);while(q...){for(v:g[u])if(color[v]<0)color[v]=color[u]^1,q.push(v);else if(color[v]==color[u])return false;}}

正确性依据

BFS层次奇偶给出颜色。若存在同色边，形成奇环；若无冲突，每条边跨颜色集合，得到合法二分划分。

错解反馈

只从一个分量染色；邻居已染色就跳过而不检查冲突；有自环仍判真。

迁移训练

判断边01,12,23,30,02的图。答案否，0-1-2-0构成三角形奇环。