atcoder ABC313 B - Who is Saikyo?の勉強

DFS,BFS atcoder

atcoder.jp

・参考：
AtCoder ABC 313 B - Who is Saikyo? (灰色, 300 点) - けんちょんの競プロ精進記録

・説明：
参考記事のやり方のうち2つをpythonで実装した。
1つ目は、一度も負けていない人を最強とする方法でtmpで負けた人のindexを0にする。負けていない人が複数人いると決められないので-1を出力する。これはsum(tmp)==1のとき最強が決まりtmp.index(1)でその人のindexが分かる。

2つ目はすべての点を始点にしてdfsしてすべて探索済みにできたらその始点が最強だと分かる。ここでfor文でseenを毎回初期化しないといけない。

・実装1つ目

n,m=map(int,input().split())

tmp=[1 for _ in range(n)]   #負けた人のindexを0にするので1で初期化。

#負けた人のindexを0に
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  tmp[b]=0

if sum(tmp)==1:
  print(tmp.index(1)+1)  #1を要素に持つ人のindexを取ってくる
else:
  print(-1)

・実装2つ目

#参考：https://drken1215.hatenablog.com/entry/2023/08/05/234100
n,m=map(int,input().split())
g=[[]for _ in range(n)]

for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  g[a].append(b)

def dfs(v,seen):
  seen[v]=1
  for nv in g[v]:
    if seen[nv]:
      continue
    dfs(nv,seen)

for v in range(n):
  seen=[0 for _ in range(n)]  #探索済みかのリスト。0で初期化。
  dfs(v,seen)
  if sum(seen)==n:   #全部の探索済みにできたら。
    print(v+1)
    exit()
print(-1)