-
Объединение, пересечение и разность множеств
(50 задач)
Формула включения-исключения
(42 задачи)
Мощность множества. Взаимно-однозначные отображения
(38 задач)
Необычные конструкции
(14 задач)
Теория множеств (прочее)
(16 задач)
Фильтр
Выбрано 2 задачи Убрать все задачи
Задан неориентированный граф с 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
РешениеВ саду у Ани и Вити росло 2006 розовых кустов. Витя полил половину всех кустов, и Аня полила половину всех кустов. При этом оказалось, что ровно три куста, самые красивые, были политы и Аней, и Витей. Сколько розовых кустов остались не политыми?
Решение
Задачи
Задача 88234 |
|
|
В первом пенале лежат лиловая ручка, зелёный карандаш и красный ластик; во втором – синяя ручка, зелёный карандаш и жёлтый ластик; в третьем – лиловая ручка, оранжевый карандаш и жёлтый ластик. Содержимое этих пеналов характеризуется такой закономерностью: в каждых двух из них ровно одна пара предметов совпадает и по цвету, и по назначению. Что должно лежать в четвёртом пенале, чтобы эта закономерность сохранилась? (В каждом пенале лежит ровно три предмета: ручка, карандвш и ластик.)
|
|
Решение |
Задача 65328 |
|
|
Аня ждёт автобус. Какое событие имеет наибольшую вероятность?
А = {Аня ждёт автобус не меньше минуты},
В = {Аня ждёт автобус не меньше двух минут},
С = {Аня ждёт автобус не меньше пяти минут}.
|
|
|
Решение |
Задача 87939 |
|
|
|
|
|
Решение |
Задача 103738 |
|
|
|
|
|
Решение |
Задача 104074 |
|
|
В саду у Ани и Вити росло 2006 розовых кустов. Витя полил половину всех кустов, и Аня полила половину всех кустов. При этом оказалось, что ровно три куста, самые красивые, были политы и Аней, и Витей. Сколько розовых кустов остались не политыми?
|
|
|
Решение |
Страница: 1 2 3 4 5 6 7 >> [Всего задач: 150]
