Дистанционный практикум по программированию

Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:
    а) выясняет количество компонент связности графа;
    б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
    в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
    г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
    д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Исходные данные

Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа, заданных номерами концевых вершин.

Результат

Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
    в первой строке запишите ответ на пункт а);
    во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
    в следующую строку выведите сообщение "NOT POSSIBLE", если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение "POSSIBLE";
    далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
    в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем - номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся. Баллы за пункт в) в случае утвердительного ответа на него начисляются лишь в том случае, если программа правильным образом ориентировала ребра графа (пункт г).

Пример

Решение

Ребро, удаление которого увеличивает число компонент связности графа, называется мостом. Если граф не содержит мостов, то он называется реберно-двусвязным. Ясно, что произвольный связный граф разбивается на компоненты реберной двусвязности (т.е. максимальные реберно-двусвязные подграфы), соединенные мостами [Емеличев 90, п. 34]. При этом каждая вершина принадлежит в точности одной компоненте и каждое ребро, не являющееся мостом, входит только в одну компоненту. Описанное разбиение графа может быть осуществлено с помощью обхода в глубину, аналогично поиску обычных компонент двусвязности графа [Липский 88, п. 2.6].

Понятно и то, что граф, содержащий мост, нельзя ориентировать требуемым в пункте в) способом. С другой стороны, любой реберно-двусвязный граф ориентировать таким образом можно. Для этого нужно выполнить обход в глубину из произвольной вершины r, ориентируя все ребра графа, принадлежащие глубинному остовному дереву, по направлению от r, а все ребра, ему не принадлежащие, – по направлению к r. (Докажите, что полученный граф будет сильно связным.) Таким образом, ответ на пункт в) положителен в том и только том случае, когда граф не содержит мостов.

Теперь ясно, что в пункте г) нужно ориентировать все реберно-двусвязные компоненты, а все мосты оставить неориентированными. Следовательно, пункты а)-г) могут быть решены все вместе сравнительно простой модификацией обхода в глубину.

Перейдем теперь к менее очевидному пункту д). Пусть заданный граф связен. Будем рассматривать его структуру «с точностью до реберно-двусвязных компонент», стянув каждую такую компоненту в одну новую «супервершину». При этом мы получим связный ациклический граф, т.е., попросту говоря, дерево (эта процедура стягивания компонент очень похожа на построение конденсации графа [Кристофидес 78, п. 2.3]). Обозначим через k количество висячих (т.е. степени 1) вершин этого дерева. Процесс добавления к исходному графу ребер требуемым в пункте д) способом можно мыслить как добавление ребер к рассматриваемому дереву. Поскольку в итоге не должно остаться ни одной висячей вершины, то к графу необходимо добавить не менее [k/2] ребер.

С другой стороны, такого количества ребер достаточно. Докажем это. Утверждение очевидно для деревьев с k = 2 и k = 3. Рассмотрим теперь
добавление к дереву с k > 3 ребра, соединяющего две его висячие вершины u и v. После добавления образуется граф с одним циклом (т.е. реберно-двусвязной компонентой), который мы также стянем, получив новое дерево. Если вершина, полученная в результате этого стягивания, в новом дереве не является висячей, значит добавленное ребро уменьшило количество висячих вершин на две. В противном случае назовем висячую вершину v плохой для u (а вершину u – плохой для v), и для сокращения числа висячих вершин на две нам следует искать другую пару (u, v). Однако оказывается, что для каждой висячей вершины u может существовать не более одной плохой висячей вершины v (покажите это). 

Таким образом, всегда можно добавить ребро, уменьшающее число висячих вершин на две. Это завершает доказательство сформулированного утверждения. Случай, когда исходный граф несвязен, разбирается аналогично.