Module: Search in depth. DFS


Problem

5 /12


bipartite graph

Theory Click to read/hide

Bipartite graph
 
Bipartite graph - a graph whose vertices can be divided into two sets so that each edge connects the vertices from different sets.


Often in the context of bipartite graphs, the concept of colors vertices is used. Splitting a graph into two parts is called coloring its vertices with two different colors. Each edge must connect vertices of a different color.

DFS. 
 

Algorithm

We start painting from an arbitrary vertex, which we paint in an arbitrary color.
When passing along each edge, paint the next vertex in the opposite color.
If, while iterating over neighboring vertices, we find a vertex that is already painted in the same color as the current one, then there is an odd cycle in the graph, which means that it is not bipartite.

Problem

A graph is called bipartite if its vertices can be colored in two colors so that there are no edges connecting vertices of the same color (that is, each edge goes from the vertex of the 1st color to the vertex of the 2nd).
Given a graph. It is required to check whether it is bipartite, and if so, color its vertices.
 
Input
The first line first contains the number N - the number of graph vertices (does not exceed 100). Next comes the adjacency matrix - a NxN matrix of 0 and 1 (0 means no edge, 1 means presence). The graph is undirected, without loops.
 
Imprint 
On the first line print one of the messages YES or NO (depending on whether the graph is bipartite or not). If the answer is YES, in the second line print N numbers - the colors to color the vertices: for the first color use the value 1, for the second color - the value 2. The first vertex should be color 1.
 
Examples
# Input Output
1
3
0 1 1
1 0 1
1 1 0
 NO
2
3
0 1 1
1 0 0
1 0 0
YES
1 2 2

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!