PythonでABC168Dを解く

はじめに

昨日のABCで解けなくて、悔しくて夜も眠れなかったので復習します。

.. (Double Dots)

考えたこと
制約より、どの部屋間も複数の道を使えば移動可能なので与えられるグラフは連結しています。連結しているグラフなら、必ず構築かのうになります。print('No')で提出すると0ACです。
解法は、道標は1から同じ深さごとに探索して自分よりも深い部屋に到達したら、自分の部屋への道標を置いていけば解けます。これは、BFSで簡単に実装できます。

verはver[i]から1回で到達できる部屋のリスト

from collections import deque
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

q = deque([])
path = [-1] * n
ver = [[] for _ in range(n)]
for i in range(m):
    ab[i].sort()
    if ab[i][0] == 1:
        q.append([ab[i][0]-1,ab[i][1]-1])
        #path[ab[i][1]-1] = 1
    ver[ab[i][0]-1].append(ab[i][1]-1)
    ver[ab[i][1]-1].append(ab[i][0]-1)

def bfs(q, visited_list):
    while len(q) > 0:
        now = q.popleft()
        go = now[1]
        if visited_list[go] == -1:
            visited_list[go] = now[0]+1
            for i in range(len(ver[go])):
                q.append([go,ver[go][i]])
    return visited_list
ans = bfs(q,path)
print('Yes')
for i in range(1,n):
    print(ans[i])

計算量は$O(N+M)$

まとめ

非常に基礎的な問題でした。昨日は、空回りしてた感があったので次のAGCで1完目指してがんばります。ではまた。

余談

グラフの問題はこれを使うと考えやすいです。