Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Двудольный граф

Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го)
 
Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.
 
Входные данные
В первой строке задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель.
 
Выходные данные
В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет). В случае ответа YES во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины.

Ввод Вывод
3
0 1 1
1 0 1
1 1 0
NO
3
0 1 1
1 0 0
1 0 0
YES
1 2 2
 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: