Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:
    а) выясняет количество компонент связности графа;
    б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
    в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
    г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
    д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа, заданных номерами концевых вершин.

Выходные данные
Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
    в первой строке запишите ответ на пункт а);
    во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
    в следующую строку выведите сообщение «NOT POSSIBLE», если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение «POSSIBLE»;
    далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
    в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем – номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся. Баллы за пункт в) в случае утвердительного ответа на него начисляются лишь в том случае, если программа правильным образом ориентировала ребра графа (пункт г).

Пример входного файла
4
1 2
2 4
3 4
4 1

Пример выходного файла
1
1
3 4
NOT POSSIBLE
3
1 2
2 4
4 1
1
1 3

   Решение

Выставка кошек. На кошачьей выставке каждая третья кошка белая. Каждое шестое белое животное — кошка. Кого больше: белых животных или кошек?

   Решение

Страница: 1 2 >> [Всего задач: 8]      

Выставка кошек. На кошачьей выставке каждая третья кошка белая. Каждое шестое белое животное — кошка. Кого больше: белых животных или кошек?

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

Решение

Обезьянки – Маша, Даша, Глаша и Наташа – съели на обед 16 мисочек манной каши. Каждой обезьянке что-то досталось. Глаша и Наташа вместе съели 9 порций. Маша съела больше Даши, больше Глаши и больше Наташи. Сколько мисочек каши досталось обезьянке Даше?

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

Решение

Сказка о царе Салтане. В подвалах Князя Гвидона среди мешков с золотыми монетами, отлитыми из ореховых скорлупок, затесался один, в котором все монеты фальшивые. И мешок, и монеты выглядят точно так же, как настоящие, но настоящая монета весит 20 золотников, а фальшивая — 15. Как с помощью одного (!) взвешивания определить, в каком мешке фальшивые монеты?

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

Решение

В пяти корзинах А, Б, В, Г и Д лежат яблоки пяти разных сортов. В каждой из корзин А и Б находятся яблоки 3 и 4 сорта, в корзине В — 2 и 3, в корзине Г — 4 и 5, в корзине Д — 1 и 5. Занумеруйте корзины так, чтобы в первой корзине имелись яблоки 1-го сорта (как минимум одно), во второй корзине — яблоки 2-го сорта и т.д.

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

Решение

Вся семья выпила по полной чашке кофе с молоком, причём Катя выпила четверть всего молока и шестую часть всего кофе.
Сколько человек в семье?

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

Решение

Страница: 1 2 >> [Всего задач: 8]