Задача 102884
|
Название задачи: Четный граф . |
 |
Условие
Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:a) определяет, является ли заданный граф четно-нечетным;
б) В случае отрицательного ответа на пункт а) находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X выполняется следующее условие: все пути между i и j состоят из четного числа ребер.
Входные данные
Первая строка входного файла содержит число вершин графа N (1 ≤ N ≤ 100), а каждая последующая – пару чисел (i, j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j.
Выходные данные
Первая строка выходного файла должна содержать ответ на пункт А в форме YES/NO. В случае отрицательного ответа на пункт А вторая строка должна содержать количество вершин в множестве X, а третья – номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.
Пример входного файла
3
1 2
Пример выходного файла
NO
2
2 3
Решение
Скачать архив тестов и решенийВыполняем обход графа в глубину (см., например, [Липский 88, п. 2.2]), одновременно раскрашивая вершины в белый и черный цвета в «шахматном порядке». А именно, пусть мы пришли в очередную вершину из вершины, имеющей, для определенности, черный цвет. Тогда красим ее в белый цвет и перебираем по очереди все соседние вершины. Если какая-то из них окрашена в черный цвет, то пропускаем ее, если в белый – выводим сообщение о том, что граф четно-нечетный и выходим из программы. Если же попадется неокрашенная вершина, то переходим в нее, выполняя тем самым шаг обхода в глубину.
Окрасив все компоненты связности, для каждой из них выберем наибольшее по мощности из множеств ее черных и белых вершин. Объединив все выбранные множества, получим, очевидно, ответ на пункт б) задачи.
Фактически, граф, не являющийся четно-нечетными, – это просто двудольный граф, а наша раскраска помогает выделить его доли. Если для каждой компоненты связности выделить левую и правую долю можно двумя способами, то для всего графа вариантов сделать это 2k , где k – число компонент связности.
