Все источники
>>
Кружки, факультативы, спецкурсы
>>
Кружки МЦНМО
>>
6 класс
>>
2004/2005
>>
Занятие 13.
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:
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
Решение
Убрать все задачи
Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:
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
Решение
Задачи
Страница: 1 2 >> [Всего задач: 7]
Среди 4-х людей нет трех с одинаковым именем, одинаковым отчеством или одинаковой фамилией, но у любых двух людей совпадают либо имя, либо отчество, либо фамилия. Может ли так быть?
Продолжите последовательность: 2, 6, 12, 20, 30, …
Страница: 1 2 >> [Всего задач: 7]
Задача 103881 (#13.1) |
|
|
Один мальчик 16 февраля 2003 года сказал: "Разность между числами прожитых мною (полных) месяцев и прожитых (полных) лет сегодня впервые стала равна 111". Когда он родился?
|
|
Решение |
Задача 53346 (#13.3) |
|
|
Верно ли утверждение: "Если две стороны и три угла одного треугольника равны двум сторонам и трём углам другого треугольника, то такие треугольники равны"?
|
|
|
Решение |
Задача 103752 (#13.4) |
|
|
На Нью-Васюковской валютной бирже за 11 тугриков дают 14 динаров, за 22 рупии – 21 динар, за 10 рупий – 3 талера, а за 5 крон – 2 талера. Сколько тугриков можно выменять за 13 крон?
|
|
|
Решение |
Задача 98670 (#13.5) |
|
|
|
|
|
Решение |
Задача 98671 (#13.6) |
|
|
|
|
|
Решение |
Страница: 1 2 >> [Всего задач: 7]
