公式
C - Tour 解説 by en_translator
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;
}
投稿日時:
最終更新: