Версия для печати
Убрать все задачи

---

Задан неориентированный граф с 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,  то у десятичного представления дроби ¹/_m нет предпериода.

   Решение

---

Натуральное число $k$ назовём интересным, если произведение первых $k$ простых чисел делится на $k$ (например, произведение первых двух простых чисел – это  2·3 = 6,  и 2 – число интересное).
Какое наибольшее количество интересных чисел может идти подряд?

   Решение

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 67013

Тема:   [ Простые числа и их свойства ]

Сложность: 3 Классы: 7,8,9,10

Найдите наибольшее натуральное $n$, обладающее следующим свойством: для любого простого нечетного $p$, меньшего $n$, разность  $n - p$  также является простым числом.

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

Решение

---

Задача 67038

Темы:   [ Делимость чисел. Общие свойства ] [ Количество и сумма делителей числа ]

Сложность: 3 Классы: 8,9

Турнир Городов проводится раз в год. Сейчас год проведения осеннего тура делится на номер турнира:  2021:43 = 47.  Сколько ещё раз человечество сможет наблюдать это удивительное явление?

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

Решение

---

Задача 67039

Темы:   [ Объем параллелепипеда ] [ Вычисление объемов ]

Сложность: 3 Классы: 8,9,10,11

Дан куб. Три плоскости, параллельные граням, разделили его на 8 параллелепипедов. Их покрасили в шахматном порядке. Объёмы чёрных параллелепипедов оказались равны 1, 6, 8, 12.
Найдите объёмы белых параллелепипедов.

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

Решение

---

Задача 67043

Темы:   [ Делимость чисел. Общие свойства ] [ Основная теорема арифметики. Разложение на простые сомножители ]

Сложность: 3 Классы: 8,9,10,11

Натуральное число $k$ назовём интересным, если произведение первых $k$ простых чисел делится на $k$ (например, произведение первых двух простых чисел – это  2·3 = 6,  и 2 – число интересное).
Какое наибольшее количество интересных чисел может идти подряд?

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

Решение

---

Задача 67063

Темы:   [ Основная теорема арифметики. Разложение на простые сомножители ] [ Признаки делимости на 5 и 10 ]

Сложность: 3 Классы: 7,8,9,10

Петя взял произвольное натуральное число, умножил его на 5, результат снова умножил на 5, потом ещё на 5, и так далее.
Верно ли, что с какого-то момента все получающиеся у Пети числа будут содержать 5 в своей десятичной записи?

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

Решение

---

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями