Алгоритм решения этой задачи основан на выделении в конденсации графа истоков, стоков и изолированных вершин и их соединении в определенном порядке. Асимптотика O(n+m). Алгоритм подробно описан в статье "A Note on Eswaran and Tarjan's Algorithm for the Strong Connectivity augmentation problem" (S. Raghavan). В русскоязычном сегменте сети, видимо, ничего адекватного нет.

Мне кажется, что можно построить таким образом.

Новый граф, представленный в виде компонент сильной связности, будет ориентированным и ациклическим. Проведем топологическую сортировку вершин в новом графе. Найдем все вершины, из которых нельзя перейти в другую вершину, назовем их условно "листьями". Найдем все вершины, в которые нельзя перейти из других вершин, назовем их условно "корнями". Если пронумеровать компоненты связности нового графа от 1 до N, то искомые ребра будут выглядеть таким образом:

"лист 1" — "лист 2" — ... — "лист N" — "корень N" — "корень N — 1" — ... — "корень 1". Это даст возможность добраться из любой вершины до любой: спуститься до листьев, пройти до "листа N", подняться до "корня N", пройти до нужного "корня", спуститься к интересующей вершине.

Если вопрос в асимптотике, то решается он выкидыванием ненужного, из всех рёбер входящих в нижнюю компоненту достаточно оставить одно, из всех рёбер исходящих из верхней компоненты тоже достаточно оставить одно, ответ же от этого не меняется. (По факту, довыкидывать можно до состояния набора кустов растущих ввер, набора кустов растущих вниз и отдельных вершин, всё это можно соединить конструктивно по циклу, а потом дополнив листья; но уже не нужно достаточно довыкидывать рёбер до 2* кол-во вершин.) Далее, соединять по циклу, поскольку рёбер мало, то мёрдж компонент будет быстр.