Первое что пришло на ум: запустим дфс из произвольной вершины, для каждого ребра сохраним в каком направлении оно было первый раз рассмотрено этим дфсом (v → u или u → v) и построим ориентированный граф. Дальше найдём в нём компоненты сильной связности и сожмём их в одну вершину.

Граф ориентированный или нет? В любом случае за линейное время это делается выделением компонент сильной связности (для орграфов) и компонент реберной двусвязности (для неор графов, это почти тоже самое, что и мосты выделить) известными алгоритмами. Компоненты надо занумеровать, а затем пройтись по всем ребрам и добавить их в граф-результат, соединив вершины соответствующие номерам соединяемых компонент в оригинальном графе.

Недавно на CodeChef была задача на что-то похожее. Может будет полезно.

Думаю это можно сделать с помощью СНМ ищем мосты и проверяем все ребра если это не мост то отправляем его в СНМ потом опять проверяя все ребра берем их лидеров и в новом сжатом графе создаем ребро между лидерами так можно быстро получить новый сжатый граф Извиняюсь за неграмотность