Explanation

Let's first compose the graph into many SCCs and construct the corresponding DAG with SCCs as vertices. The problem boils down to: How many edges will we need to add in the DAG such that the DAG becomes strongly connected?

From now on we will only consider the DAG. A node is a source if it has no incoming connections. On the other hand, a node is a sink if it has no outgoing connections. Let $S$ denote the set of sources and $T$ denote the set of sinks. We should only add edges that goes from a sink to a source (otherwise, any other edges that we add can be replaced with edges that goes from a sink to a source and connect more vertices).

For each vertex $u \in S$, we should find a unique vertex $b \in T$ that it can reach. The sink it matches with can be arbitrary but it should only travel through vertices that have not been visited yet. Note that it may be the case that each source cannot be matched to a unique sink. For now, we've created many pairs $(u_i, v_i)$. With these pairs, one optimal construction is to add edges $v_i \rightarrow u_{i-1}$ for each $i \geq 2$ and $v_1 \rightarrow u_k$. This way, we create a "ring" where we can guarantee for all vertex that $u_i$, it can also reached by all vertices that is reachable from $u_{i+1}$. This is strongly connected because of the $v_1 \rightarrow u_k$ edge. If we have a pair of vertices $(a, b)$ such that $b$ was reachable from $a$ but $a$ was not reachable from $b$ in the original graph, now we can start from $b$ and travel around the ring to $a$.

However, there may be some sources and sinks that were not originally matched. We can connect each sink to a unique source with an edge so that their components are strongly connected. For any sources or sinks that still remain, we can just connect them to the new graph by adding an edge. Note that whether we connect a source or a sink to the main graph, the connection will propagate to the rest of the vertices in their SCCs.

Thus, the minimum number of edges we must add is $\max(|S|,|T|)$. As an exercise, prove why it is optimal.

Implementation

Time Complexity: $\mathcal{O}(N + M)$

Copy
#include <bits/stdc++.h>
using namespace std;

struct SCC {
	vector<vector<int>> adj, c_adj, r_adj;
	vector<int> c, v, ord;

	SCC(vector<vector<int>> _adj) : adj(_adj) {}

	void dfs(int i) {