Задан неориентированный граф с 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 внутри окружности делит хорду этой окружности на отрезки, равные a и b. Через точку M проведена хорда AB, делящаяся точкой M пополам. Найдите AB.

   Решение

На окружности дано n точек. Через центр масс n - 2 точек проводится прямая, перпендикулярная хорде, соединяющей две оставшиеся точки. Докажите, что все такие прямые пересекаются в одной точке.

   Решение

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

На сторонах AB, BC и CA треугольника ABC взяты точки C₁, A₁ и B₁ так, что прямые CC₁, AA₁ и BB₁ пересекаются в некоторой точке O. Докажите, что:
а) = + ;
б) ^{. .} = + + + 28.

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

Решение

На сторонах BC, CA и AB треугольника ABC взяты точки A₁, B₁ и C₁ так, что BA₁/A₁C = CB₁/B₁A = AC₁/C₁B. Докажите, что центры масс треугольников ABC и A₁B₁C₁ совпадают.

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

Решение

В середины сторон треугольника ABC помещены точки, массы которых равны длинам сторон. Докажите, что центр масс этой системы точек расположен в центре вписанной окружности треугольника с вершинами в серединах сторон треугольника ABC.
Замечание. Центр масс системы точек, рассматриваемой в задаче 14.12.1 совпадает с центром масс фигуры, изготовленной из трех тонких стержней одинаковой толщины. Действительно, при нахождении центра масс стержень можно заменить на точку, расположенную в середине стержня и имеющую массу, равную массе стержня. Ясно также, что масса стержня пропорциональна его длине.

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

Решение

На окружности дано n точек. Через центр масс n - 2 точек проводится прямая, перпендикулярная хорде, соединяющей две оставшиеся точки. Докажите, что все такие прямые пересекаются в одной точке.

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

Решение

На прямых $BC$, $CA$, $AB$ взяты точки $A_1$ и $A_2$, $B_1$ и $B_2$, $C_1$ и $C_2$ так, что $A_1B_2\| AB$, $B_1C_2\| BC$, $C_1A_2\| CA$. Пусть $\ell_a$ — прямая, соединяющая точки пересечения прямых $BB_1$ и $CC_2$, $BB_2$ и $CC_1$; прямые $\ell_b$ и $\ell_c$ определяются аналогично. Докажите, что прямые $\ell_a$, $\ell_b$ и $\ell_c$ пересекаются в одной точке (или параллельны).

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

Решение

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