Фильтр
Выбрано 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
Решение
Решение
Убрать все задачи
Задан неориентированный граф с 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
РешениеСаша пригласил Петю в гости, сказав, что живёт в 10-м подъезде в квартире №333, а этаж сказать забыл. Подойдя к дому, Петя обнаружил, что дом девятиэтажный. На какой этаж ему следует подняться? (На каждом этаже число квартир одинаково, номера квартир в доме начинаются с единицы.)
Решение
Задачи
Страница: 1 2 3 >> [Всего задач: 12]
Доктор Айболит раздал четырём заболевшим зверям 2006 чудодейственных таблеток. Носорог получил на одну больше, чем крокодил, бегемот на одну больше, чем носорог, а слон — на одну больше, чем бегемот. Сколько таблеток придётся съесть слону?
Разрежьте фигуру (см. рисунок) на две одинаковые (совпадающие при наложении) части.
Разрежьте изображённый на рисунке пятиугольник на две одинаковые (совпадающие при наложении) части.
Страница: 1 2 3 >> [Всего задач: 12]
Задача 104057 |
|
|
|
|
Решение |
Задача 104058 |
|
|
|
|
|
Решение |
Задача 104059 |
|
|
Саша пригласил Петю в гости, сказав, что живёт в 10-м подъезде в квартире №333, а этаж сказать забыл. Подойдя к дому, Петя обнаружил, что дом девятиэтажный. На какой этаж ему следует подняться? (На каждом этаже число квартир одинаково, номера квартир в доме начинаются с единицы.)
|
|
|
Решение |
Задача 104063 |
|
|
Винни-Пух и Пятачок поделили между собой торт. Пятачок захныкал, что ему досталось мало. Тогда Пух отдал ему треть своей доли. От этого у Пятачка количество торта увеличилось втрое. Какая часть торта была вначале у Пуха и какая у Пятачка?
|
|
|
Решение |
Задача 104064 |
|
|
|
|
|
Решение |
Страница: 1 2 3 >> [Всего задач: 12]
