そまちょブログのそまちょ（@somachob）です。
この記事は、AtCoder Beginner Contest 313 の B問題についての解説です。
C問題について解説した記事もあります。
B – Who is Saikyo?
「人 Ai は人 Bi より強い」という問題文から、B で出てきた人は最強ではありません。
このことから入力が終わったときに、Bで出てきていない人が最強になります。
Bで出てきていない人が複数のときは、最強のプログラマーが複数人いるということになります。
これを実装したコードです。
N, M = map(int, input().split())
# 最強かを管理する変数
# 初めはみんな最強
saikyo= [True] * N
for _ in range(M):
A, B = map(int, input().split())
A -= 1
B -= 1
# B は最強ではない
saikyo[B] = False
# 最強のプログラマーが複数人のとき
if saikyo.count(True) != 1:
print(-1)
exit()
# 最強プログラマーが何番目の人か特定
for i in range(N):
if saikyo[i]:
print(i+1)変数 saikyo で最強かどうかを管理しています。
saikyo[0]は人１が最強かどうか、saikyo[1]は人２が最強かどうかを管理します。
初めは、全員を最強（＝True）で初期化します。
saikyo= [True] * N次に入力を受け取り、Bで出てきた人を最強ではない（＝False）に変更していきます。
for _ in range(M):
A, B = map(int, input().split())
A -= 1
B -= 1
# B は最強ではない
saikyo[B] = False 入力を受け取ったあとは、最強の人が１人でないときは、‐１を出力します。
count で True の数を取得できます。
# 最強のプログラマーが複数人のとき
if saikyo.count(True) != 1:
print(-1)
exit()最強の人が１人のときは、その番号を出力します。saikyo[0] が True のときは人１が最強になるので、i + 1 になることに注意してください。
# 最強プログラマーが何番目の人か特定
for i in range(N):
if saikyo[i]:
print(i+1)グラフとして解く
この問題は、深さ優先探索や幅優先探索をして解くこともできます。
入力を有向グラフとして受け取ります。
ある頂点から探索を開始して、すべての頂点に訪れることができれば、その頂点が最強のプログラマーになります。
from collections import deque
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
A, B = map(int, input().split())
A -= 1
B -= 1
graph[A].append(B)
# 幅優先探索
def bfs(start):
queue.append(start)
visited[start] = True
while queue:
v = queue.popleft()
for next_v in graph[v]:
# 探索済みのとき
if visited[next_v]:
continue
queue.append(next_v)
visited[next_v] = True
# すべての頂点から幅優先探索
for i in range(N):
# 変数の初期化
queue = deque()
visited = [False] * N
bfs(i)
# すべての頂点を探索できたとき
if False not in visited:
print(i + 1)
exit()
# 最強の人が複数
print(-1)幅優先探索について、解説した記事もあるので参考にしてください。
