Фильтр
Выбрано 3 задачи Убрать все задачи
Задан неориентированный граф с 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
РешениеДокажите, что если (m, 10) = 1, то у десятичного представления дроби 1/m нет предпериода.
РешениеНатуральное число $k$ назовём интересным, если произведение первых $k$ простых чисел делится на $k$ (например, произведение первых двух простых чисел – это 2·3 = 6, и 2 – число интересное).
Какое наибольшее количество интересных чисел может идти подряд?
Решение
Задачи
Задача 116779 |
|
|
В каком году установлен памятник Юрию Долгорукому, если в записи этого числа последняя цифра на единицу меньше предыдущей и при зачеркивании первой и последней цифры получается наибольшее двузначное число с суммой цифр 14?
|
|
Решение |
Задача 116781 |
|
|
Длина крокодила от головы до хвоста в три раза меньше десяти кэн, а от хвоста до головы равна трем кэн и двум сяку. Известно, что одна сяку равна 30 см. Найдите длину крокодила в метрах. (Кэн и сяку – японские единицы длины.)
|
|
|
Решение |
Задача 116786 |
|
|
Иван, Петр и Сидор ели конфеты. Их фамилии – Иванов, Петров и Сидоров. Иванов съел на 2 конфеты меньше Ивана, Петров – на 2 конфеты меньше Петра, а Петр съел больше всех. У кого из них какая фамилия?
|
|
|
Решение |
Задача 116780 |
|
|
Квадратный лист размером 6×6 клеток сложили и вырезали из него часть так, как показано на рисунке. Затем этот лист развернули. Нарисуйте развёрнутый лист размером 6×6 клеток и покажите на рисунке сделанные вырезы.
|
|
|
Решение |
Задача 116782 |
|
|
Двенадцать малышей вышли во двор играть в песочнице. Каждый, кто принёс ведёрко, принёс и совочек. Забыли дома ведёрко девять малышей, забыли дома совочек двое. На сколько меньше малышей, которые принесли ведёрко, чем тех, которые принесли совочек, но забыли ведёрко?
|
|
|
Решение |
Страница: 1 2 3 >> [Всего задач: 15]
