相異なる頂点 \(a,b,c\) であって、頂点 \(a\) から頂点 \(b\) への有向辺と頂点 \(b\) から頂点 \(c\) への有向辺がともに存在するが頂点 \(a\) から頂点 \(c\) への有向辺が存在しないようなものが存在する場合に頂点 \(a\) から頂点 \(c\) への有向辺を追加する、という操作を繰り返すのが最小回数で目的を達成する上で最適です。しかし、このシミュレーションを実行時間制限に間に合うように行うのは少し大変です。

実は、最終的なグラフの状態において存在する頂点 \(x\) を始点とする有向辺は、初期状態において頂点 \(x\) から到達可能な頂点( \(x\) を除く)を終点とするもの及びそれに限ります。

このことから、初期状態のグラフに対し、各頂点から到達可能な頂点をBFSやDFSで調べれば良いです。ある始点からのBFSやDFSは \(\mathrm{O}(M)\) で行えるため、全体の計算量は \(\mathrm{O}(NM)\) となります。

実装例(C++, BFSによる実装)

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

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<vector<int>> E(N);
	
	for(int i=0;i<M;i++){
		int u,v;
		cin>>u>>v;
		E[u-1].push_back(v-1);
	}
	
	int ans = 0;
	
	for(int i=0;i<N;i++){
		vector<bool> f(N,false);
		f[i] = true;
		queue<int> Q;
		Q.push(i);
		
		while(Q.size()>0){
			int x = Q.front();
			Q.pop();
			for(int j=0;j<E[x].size();j++){
				int y = E[x][j];
				if(f[y])continue;
				f[y] = true;
				Q.push(y);
				ans++;
			}
		}
	}
	
	ans -= M;
	cout<<ans<<endl;
	
	return 0;
}