[Python] BFS（幅優先探索） ABC168D

ABC168D

連結グラフなので、BFSの原理から最小性が保障されることに注意する。
参考
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

サンプルコード

from collections import deque
# 頂点数と辺数
N, M = map(int, input().split())
# 辺
AB = [map(int, input().split()) for _ in range(M)]
# 無向グラフの隣接リスト設定
link = [[] for _ in range(N + 1)]
for a, b in AB:
  # aとbをそれぞれ紐付け
  link[a].append(b)
  link[b].append(a)
# BFSのデータフレーム
dist = [-1] * (N + 1) # 看板未設定
que = deque([1]) # 頂点1を始点とした訪問キュー
# BFS 開始 (キューが空になるまで探索を行う)
while que:
  v = que.popleft() # キューから先頭頂点(現在地)v取得
  for i in link[v]:
   # 未設定頂点iに現在地への看板を設定し訪問キューに追加する
   # 未設定頂点iに現在地への看板を設定し、iを訪問キューに追加する
   if dist[i] == -1:
     dist[i] = v
     que.append(i)

# 結果出力（各頂点に設置する看板）
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))