Модуль: Поиск в глубину. DFS


Задача

5 /19


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

Теория Нажмите, чтобы прочитать/скрыть


Двудольный граф
 
Двудольный граф - граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.


Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.

Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS
 

Алгоритм

Начинаем покраску с произвольной вершины, которую красим в произвольный цвет.
При прохождении по каждому ребру красим следующую вершину в противоположный цвет.
Если при переборе соседних вершин мы нашли вершину, уже покрашенную в тот же цвет, что и текущая, то в графе существует нечётный цикл, а значит, он не является двудольным.

Задача

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

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64140
Java2
Python279
Комментарий учителя