Двудольный граф
Граф называется двудольным, если его вершины можно раскрасить в два цвета
так, что нет ребер, соединяющих вершины одинакового цвета (то есть
каждое ребро идет из вершины 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
|
