Module: 徹底的に検索します。 DFS


Problem

5 /12


二部グラフ

Theory Click to read/hide

二部グラフ
 
二部グラフ - 頂点が 2 つのセットに分割され、各エッジが異なるセットからの頂点。


多くの場合、2 部グラフのコンテキストでは、 色 頂点の概念が使用されます。グラフを 2 つの部分に分割することを、頂点を 2 つの異なる色で色付けすると呼びます。各エッジは、異なる色の頂点を接続する必要があります。

DFS. 
 

アルゴリズム

任意の頂点からペイントを開始し、任意の色でペイントします。
各エッジを通過するとき、次の頂点を反対の色でペイントします。
隣接する頂点を繰り返し処理しているときに、現在の色と同じ色で既にペイントされている頂点が見つかった場合、グラフに奇数のサイクルがあり、2 部構成ではないことを意味します。

Problem

グラフの頂点を 2 つの色で着色でき、同じ色の頂点を結ぶエッジが存在しない場合 (つまり、各エッジが 1 番目の色の頂点から 2 番目の色の頂点に向かう)、グラフは二部グラフと呼ばれます。 .
グラフを与えます。二部構成であるかどうかを確認し、二部構成である場合は頂点に色を付ける必要があります。
 
入力
最初の行には、最初に数字 N が含まれています。これはグラフの頂点の数です (100 を超えない)。次に隣接行列、つまり 0 と 1 からなる NxN 行列です (0 はエッジなし、1 はエッジがあることを意味します)。グラフは無向であり、ループはありません。
 
出版社
最初の行には、メッセージ YES  または NO のいずれかを出力します (グラフが 2 部構成であるかどうかに応じて)。答えが YES の場合、2 行目に N 個の数値を出力します。頂点に色を付ける色です。最初の色には値 1 を使用し、2 番目の色には値 1 を使用します。 2 番目の色 - 値 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