Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:
    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 3 4 5 6 7 >> [Всего задач: 242]      

Продолжения равных хорд AB и CD окружности соответственно за точки B и C пересекаются в точке P.
Докажите, что треугольники APD и BPC равнобедренные.

Прислать комментарий

Решение

Квадрат ABCD со стороной 2 и квадрат DEFK со стороной 1 стоят рядом на верхней стороне AK квадрата AKLM со стороной 3. Между парами точек A и E, B и F, C и K, D и L натянуты паутинки. Паук поднимается снизу вверх по маршруту AEFB и спускается по маршруту CKDL. Какой маршрут короче?

Прислать комментарий

Решение

На диагонали AC квадрата ABCD взята точка M, причём  AM = AB.  Через точку M проведена прямая, перпендикулярная прямой AC и пересекающая BC в точке H. Докажите, что  BH = HM = MC.

Прислать комментарий

Решение

В треугольнике $ABC$ $\angle C=90^{\circ}$, $A_0$, $B_0$, $C_0$ – середины сторон $BC$, $CA$, $AB$ соответственно. На отрезках $AB_0$ и $BA_0$ во внешнюю сторону построены как на основаниях равносторонние треугольники с вершинами $C_1$, $C_2$. Найдите угол $C_0C_1C_2$.

Прислать комментарий

Решение

Из вершины B произвольного треугольника ABC проведены вне треугольника прямые BM и BN, так что  ∠ABM = ∠CBN.  Точки A' и C' симметричны точкам A и C относительно прямых BM и BN (соответственно). Доказать, что  AC' = A'C.

Прислать комментарий

Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 242]