冷めたコーヒー

Weniger, aber besser

AtCoder ABC 168 D - .. (Double Dots) (400 点) in Python

幅優先探索を使う典型的な問題でした...。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の部屋が少なくとも一つは隣接しています。