解题思路

• 二分图充要条件：图中不存在奇环。
• 经典做法：对每个连通分量做 BFS/DFS 染色。起点染 0，邻点染 1，继续扩展；若遇到与已染相邻点颜色相同，则不是二分图。
• 图可能不连通，需从所有未染色点发起遍历；允许孤点。

算法步骤

• 建邻接表（1..n）。
• 颜色数组 color 初始化为 -1（未染色）。

题目描述

给定一个无向图，判断该图是否为二分图。若可将顶点集合划分为两个不相交的子集，使得任意一条边的两个端点分属不同子集，则该图为二分图。