AtCoder Beginner Contest 204 C - Tour【Python】
https://atcoder.jp/contests/abc204/tasks/abc204_c
AtCoder ProblemsのRecommendationでDifficulty: 629、Solve Probability:
43%でした。
各都市ごとに深さ優先探索を行いました。
sys.setrecursionlimit(10 ** 7) N, M = map(int, input().split()) G = [[] for i in range(N)] for i in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append(b) ans = 0 # 再帰関数 dfs を定義する。 def dfs(i): global ans visited[i] = True for i2 in G[i]: if not visited[i2]: dfs(i2) # 各都市ごとに深さ優先探索を行い、到達可能な都市の和を答えに加算する for i in range(N): visited = [False]*N dfs(i) ans += sum(visited) print(ans)