ABC168 D - .. (Double Dots)

問題原文

atcoder.jp

解法

部屋１から幅優先探索をすれば、各部屋まで最小の移動回数で到達できる。
逆にいうと、それを辿れば各部屋から部屋１まで最小の移動回数で到達できる。

よって、次の部屋に移るタイミングで、今いた部屋の番号を次の部屋の道しるべとして置いていけばいい。

実装

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

que = deque([0])
guideposts = [-1] * N
guideposts[0] = None

while que:
    n = que.pop()
    for to in G[n]:
        if guideposts[to] != -1:
            continue
        guideposts[to] = n
        que.appendleft(to)

print('Yes')
print(*[guisepost + 1 for guisepost in guideposts[1:]], sep="\n")

感想

コウイウノスキー！