幅優先探索を使う典型的な問題でした...。python
ではcollections
モジュールのdeque
を用いることによって実装してあげるのが最も自然なのかなと思うので、そのように実装してあげます。「幅優先探索ってそもそも何?」という方は、けんちょんさんの記事を一度読まれることをお勧めします。C++
で書かれていますが、幅優先探索の考え方はプログラミング言語に依存しないので、大いに参考になると思います。
from collections import deque
n, m = map(int, input().split())
Graph = [[] for _ in range(n + 1)] # 隣接リスト(1-index)
for i in range(m):
a, b = map(int, input().split())
Graph[a].append(b)
Graph[b].append(a)
q = deque()
q.append(1) # 頂点 1 を enque
dist = [-1] * (n + 1)
res = [0] * (n + 1)
while len(q) > 0: # queue が空になるまで繰り返す
now = q.popleft() # queue から取り出す(deque)
for edge in Graph[now]: # 隣接している頂点について
if dist[edge] != -1: # すでに書き換えられている場合は何もしない
continue
dist[edge] = dist[now] + 1
q.append(edge)
res[edge] = now
print('Yes') # `No`となることはない
for i in range(2, n + 1):
print(res[i])
注意点として、制約に「どの2部屋間も、通路をいくつか通って行き来が可能」とあるので、No
となるような場合は存在しないということです。解説(editorial)にもある通りですが、深さ(ある部屋から部屋1
に移動するために廊下を通る最小の回数)d + 1
の部屋には、深さd
の部屋が少なくとも一つは隣接しています。