e-olymp 4002. Down with cheating!

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

Input Output
1 3 2
1 2
2 3
YES
2 3 3
1 2
1 3
2 3
NO
3 12 9
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 10
11 12
YES
4 12 10
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 9
8 10
11 12
NO

bipartite graph
Illustration for the test №3notBipartiteGraph
Illustration for the test №4
 

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

  • Initially, we define all the vertices as WHITE — not processed.
  • Call the fucntion for the first vertex (in our numbering — zero).
  • Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
  • Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
  • Color all adjacent to the adjacent vertices with RED color —  we put them in the first set.
  • Repeat this until we have completed bypassing (for convenience we use queue)  — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check  all vertices which color is white.

Code

 

Links

Related Images: