Contest Duration: - (local time) (100 minutes) Back to Home

## C - Tour Editorial 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)

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;
}


posted:
last update: