深さ優先探索について - コンニャク犬の備忘録

深さ優先探索について

204c

https://atcoder.jp/contests/abc204/tasks/abc204_c

code:python

# おまじない

import sys

sys.setrecursionlimit(10000)

# 入力の読み込み

N,M=map(int,input().split())

G=[[] for i in range(N)]

# Gi は都市iから道路で直接繋がっている都市のリスト

"""

入力

3 3

1 2

2 3

3 2

"""

for i in range(M):

A,B=map(int,input().split())

GA-1.append(B-1)

#1],2,[1

# dfs

def dfs(v):

if tempv: return # 同じ頂点を2度以上調べないためのreturn

tempv=True

for vv in Gv: dfs(vv)

#配列の要素を再帰で渡してる

#最初の例だと G0の　1 を渡している

ans=0

# 都市iからスタートする場合

for i in range(N):

temp=False*N

# tempj は都市jに到達可能かどうかを表す

dfs(i)

ans+=sum(temp)

print(ans)