给定一个无向图,请判断它是否是一个二分图。
二分图定义:如果能将一个图的顶点集合分割成两个互不相交的子集,并且使得每条边的两个顶点分别属于这两个不同的子集,则该图是二分图。
第一行包含两个整数 n 和 m,分别表示图的顶点数和边数。顶点编号从 0 到 n-1。
接下来 m 行,每行包含两个整数 u 和 v,表示顶点 u 和顶点 v 之间存在一条无向边。
如果给定的图是二分图,输出 "Yes",否则输出 "No"。
数据范围
1 ≤ n ≤ 1000
0 ≤ m ≤ 10000
0 ≤ u, v < n
提示
可以使用染色法:尝试用两种颜色对图进行染色,使得相邻顶点颜色不同
注意图可能不连通,需要检查每个连通分量
可以使用 BFS 或 DFS 实现