Return to Answer

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
• Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph. Your requirement to have all the nodes belonging to some cycle looks more weak - for example, a set of SCC's, connected by edges, satisfies your goal definition.

However, it looks like allowing additional edges to connect isolated components of $G'$ can decrease the total number of these additional edges. It follows from the inequality:

$$max(m_1+m_2,n_1+n_2)\le max(m_1,n_1)+max(m_2,n_2)$$

Additionally, an example, provided by @D.W. in comments, clearly shows just that.

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
• Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• For each source $s$ find any sink $t$, reachable from the $s$, and add an edge $(t, s)$. For each sink $q$ find any source $p$, reverse-reachable from the $q$, and add an edge $(q, p)$. Remove duplicated edges if they appear. This process will give at most $m+n$ additional edges (however, according to the @D.W. comment, this number can be lowered).
• Replace each node, representing SCC, by this SCC.

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
• Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph. Your requirement to have all the nodes belonging to some cycle looks more weak - for example, a set of SCC's, connected by edges, satisfies your goal definition.

However, it looks like allowing additional edges to connect isolated components of $G'$ can decrease the total number of these additional edges. It follows from the inequality:

$$max(m_1+m_2,n_1+n_2)\le max(m_1,n_1)+max(m_2,n_2)$$

Additionally, an example, provided by @D.W. in comments, clearly shows just that.

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• Add $max(m,n)$ edges from sinks to sources in $G'$.
• Replace each node, representing SCC, by this SCC.

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• For each source $s$ find any sink $t$, reachable from the $s$, and add an edge $(t, s)$. For each sink $q$ find any source $p$, reverse-reachable from the $q$, and add an edge $(q, p)$. Remove duplicated edges if they appear. This process will give at most $m+n$ additional edges (however, according to the @D.W. comment, this number can be lowered).
• Replace each node, representing SCC, by this SCC.