第一行输入为N和M,代表无向图的点数和边数。接下来M行,表示M条边,每一行两个整数u[i], v[i],满足1 ≤ u[i], v[i] ≤ n,保证图中无重边,自环。其中保证1 ≤ N, M ≤ 100000
一行字符串,为Yes,或者No。Yes表示输入图是二分图。No表示输入图不是二分图。
5 7 1 2 2 3 3 4 4 1 4 5 5 2
Yes
如图,把1, 3, 5点染色为白,2, 4染色为黑,即可满足二分图要求,所以这个图是二分图。
5 4 1 2 2 3 3 1 4 5
No
1, 2, 3号点无论如何染色都无法满足要求,所以不是二分图。