| | | |
|
Долой списывание!
Применение обхода в глубину
Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.
У профессора записаны все пары студентов, обменявшихся записками. Требуется определить, сможет ли он разделить студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы.
Входные данные: В первой строке находятся два числа N и M - количество студентов и количество пар студентов, обменивающихся записками (1<=N<=100, 0<=M<=(N(N−1))/2. Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.
Выходные данные: Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 2
1 2
2 3
|
YES |
| 2 |
3 3
1 2
2 3
1 3
|
NO |
| |
![]()
|
|
Двудольный граф
Применение обхода в глубину
Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 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
|
| |
![]()
|