Strong connectivity augmentation

In the unweighted strong connectivity augmentation problem, the input is a directed graph and the goal is to add as few edges as possible to it to make the result into a strongly connected graph. The algorithm for the unweighted case by Eswaran and Tarjan considers the condensation of the given directed graph, a directed acyclic graph that has one vertex per strongly connected component of the given graph. Letting ${\displaystyle s}$ denote the number of source vertices in the condensation (strongly connected components with at least one outgoing edge but no incoming edges), ${\displaystyle t}$ denote the number of sink vertices in the condensation (strongly connected components with incoming but no outgoing edges), and ${\displaystyle q}$ denote the number of isolated vertices in the condensation (strongly connected components with neither incoming nor outgoing edges), they observe that the number of edges to be added is necessarily at least ${\displaystyle \max(s+q,t+q)}$. This follows because ${\displaystyle s+q}$ edges need to be added to provide an incoming edge for each source or isolated vertex, and symmetrically at least ${\displaystyle t+q}$ edges need to be added to provide an outgoing edge for each sink or isolated vertex. Their algorithm for the problem finds a set of exactly ${\displaystyle \max(s+q,t+q)}$ edges to add to the graph to make it strongly connected.^[1]

Their algorithm uses a depth-first search on the condensation to find a collection of pairs of sources and sinks, with the following properties:^[1]

• The source of each pair can reach the sink of the pair by a path in the given graph.
• Every source that is not in one of the pairs can reach a sink in one of the pairs.
• Every sink that is not in one of the pairs can be reached from a source in one of the pairs.

A minor error in the part of their algorithm that finds the pairs of sources and sinks was later found and corrected.^[4]

Once these pairs have been found, one can obtain a strong connectivity augmentation by adding three sets of edges:^[1]

• The first set of edges connects the pairs and the isolated vertices of the condensation into a single cycle, consisting of one edge per pair or isolated vertex.
• The second set of edges each connect one of the remaining sinks to one of the remaining sources (chosen arbitrarily). This links both the source and the sink to the cycle of pairs and isolated vertices at a cost of one edge per source-sink pair.
• Once the previous two sets of edges have either exhausted all sources or exhausted all sinks, the third set of edges links each remaining source or sink to this cycle by adding one more edge per source or sink.

The total number of edges in these three sets is ${\displaystyle \max(s+q,t+q)}$.^[1]