When a start city is fixed, how can we count the number of possible goal cities?

A possible goal city is reachable from the start city using zero or more roads. Such roads can be enumerated with searching algorithms like DFS (Depth-First Search) or BFS (Breadth-First Search). By avoiding checking already visited vertices more than once, it can be computed in an \(O(N+M)\) time.

Trying all the possible \(N\) initial city, the problem has been solved in a total of \(O(N(N+M))\) time.

Sample code (Python)

# Cast a spell
import sys
sys.setrecursionlimit(10000)

# Read the input
N,M=map(int,input().split())
G=[[] for i in range(N)]
# G[i] is a list of cities that is directly connected from City 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  # return to avoid inspecting the same vertex more than once
  temp[v]=True
  for vv in G[v]: dfs(vv)

ans=0

# When starting from City i...
for i in range(N):
	temp=[False]*N
	# temp[j]: is it possible to reach City j?
	dfs(i)
	ans+=sum(temp)

print(ans)

Sample code (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;
}