Problem1382--PIPI染色

1382: PIPI染色

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1190  Solved: 526
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个n个顶点m条边的连通无向图,节点编号为1~n,现在它想对这个图进行染色,要求相邻的顶点颜色不同。它想知道是否能最多用2种颜色进行染色?
题目保证没有重边和自环。


以下内容更新于2021/5/14
该题在21年943初试被出在了真题压轴题中,题面如下:
给定图G=(V,E),如果点集V能够被分为两个不相交子集V1和V2,使得V1∪V2=V,且V1中的任何两个结点在图G中没有边,V2中的任何两个结点在图G中也没有边,则称图G为一个二部图。对于任意给定的图G,设计算法判断图G是否是一个二部图,并给出时间复杂度。

Input

第一行两个整数n,m(1<=n<=1000),数据保证没有重边和自环。
接下来m行,每行两个整数,表示这条边连接的两个顶点。

Output

如果可以用最多两种颜色进行染色,输出YES,否则输出NO

Sample Input

3 3
1 2
2 3
1 3

Sample Output

NO

Source/Category