BFS · 二分图判定

BFS · 二分图判定

给一个无向图，判断它是否是二分图（能否把顶点染成两色，使每条边的两端颜色不同）。

方法：BFS，从每个未染色点出发染 0，邻居染相反色；若遇到一条边两端同色，就不是二分图。图可能不连通，要对每个连通块都做。

输入：第 1 行 V E；接下来 E 行每行 u v 表示无向边。
输出：YES（是二分图）或 NO。

例：4 4 / 0 1 / 1 2 / 2 3 / 3 0 → 输出 YES（四元环可二分）。