Module: 深入搜索。数字文件系统


Problem

5 /12


二分图

Theory Click to read/hide

二分图
 
二分图 - 一种图，其顶点可以分为两组，因此每条边连接来自不同集合的顶点。


通常在二分图的上下文中，会使用 颜色 顶点的概念。将图形分成两部分称为 着色 其顶点具有两种不同的颜色。每条边必须连接不同颜色的顶点。

DFS. 
 

算法

我们从任意顶点开始绘制，我们用任意颜色绘制。
当沿着每条边通过时，用相反的颜色绘制下一个顶点。
如果在迭代相邻顶点时，我们发现一个顶点已经被涂上了与当前顶点相同的颜色，那么图中存在一个奇数循环，这意味着它不是二分的。

Problem

如果图的顶点可以用两种颜色着色，这样就没有边连接相同颜色的顶点（也就是说，每条边从第一种颜色的顶点到第二种颜色的顶点），则该图称为二分图.
给定一个图表。需要检查它是否是二分的，如果是，则为其顶点着色。
 
输入
第一行首先包含数字 N - 图的顶点数（不超过 100）。接下来是邻接矩阵 - 0 和 1 的 NxN 矩阵（0 表示没有边，1 表示存在）。该图是无向的，没有循环。
 
印记 
在第一行打印一条消息 YES  或 NO（取决于图是否是二分图）。如果答案是 YES， 在第二行中打印 N 数字 - 为顶点着色的颜色： 对于第一种颜色，使用值 1，对于第二种颜色 - 值 2。 第一个顶点应该是颜色 1。
 
例子
<头> <日># <正文>

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!

输入 输出
1
3
0 1 1
1 0 1
1 1 0
 没有
2
3
0 1 1
1 0 0
1 0 0
是
1 2 2