hzCPPOJ

二分图检测

时间限制:  1 s      内存限制:   128 MB
提交:2     正确:2     分值:100

题目描述

给定一个无向图,请判断它是否是一个二分图。

二分图定义:如果能将一个图的顶点集合分割成两个互不相交的子集,并且使得每条边的两个顶点分别属于这两个不同的子集,则该图是二分图。

输入

第一行包含两个整数 n 和 m,分别表示图的顶点数和边数。顶点编号从 0 到 n-1。

接下来 m 行,每行包含两个整数 u 和 v,表示顶点 u 和顶点 v 之间存在一条无向边。

输出

如果给定的图是二分图,输出 "Yes",否则输出 "No"。

样例

样例输入:
4 4 0 1 1 2 2 3 3 0
样例输出:
Yes
样例输入:
3 3 0 1 1 2 2 0
样例输出:
No
样例输入:
5 4 0 1 1 2 2 3 3 4
样例输出:
Yes

提示

数据范围

提示

提交人

AmberXie

来源/分类