スタート地点を固定したときゴール地点にできる都市の個数を数えることを考えてみましょう。

ゴール地点にできる都市は、スタート地点からいくつかの道路を使って到達できるような都市です。そのような都市は、DFSやBFSなどの探索アルゴリズムを用いて求めることができます。この際、既にチェックした頂点を2度以上調べないようにすることで、\(O(N+M)\) で求めることができます。

どの都市をスタート地点とするか \(N\) 通り全てを試すことで、全体で \(O(N(N+M))\) で問題が解けました。

実装例(Python)

# おまじない
import sys
sys.setrecursionlimit(10000)

# 入力の読み込み
N,M=map(int,input().split())
G=[[] for i in range(N)]
# G[i] は都市iから道路で直接繋がっている都市のリスト
for i in range(M):
  A,B=map(int,input().split())
  G[A-1].append(B-1)

# dfs
def dfs(v):
  if temp[v]: return  # 同じ頂点を2度以上調べないためのreturn
  temp[v]=True
  for vv in G[v]: dfs(vv)

ans=0

# 都市iからスタートする場合
for i in range(N):
	temp=[False]*N
	# temp[j] は都市jに到達可能かどうかを表す
	dfs(i)
	ans+=sum(temp)

print(ans)

実装例(C++)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=2000;

vector<vector<int>>G;
bool temp[MAX_N];
void dfs(int v){
	if(temp[v])return;
	temp[v]=true;
	for(auto vv:G[v])dfs(vv);
}

int main(){
	int N,M;
	cin >> N >> M;
	G.resize(N);
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a >> b;
		G[a-1].push_back(b-1);
	}

	int ans=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++)temp[j]=false;
		dfs(i);
		for(int j=0;j<N;j++)if(temp[j])ans++;
	}
	
	cout << ans;
}