ABC167「D - .. (Double Dots)」を個別に見直す

と言っても、解説や他の人の回答見てほぼ写経しただけだけど。

問題

は、以下のリンク先を見てもらった方がはやい。

D - .. (Double Dots)

所感

「BFS木」ちゅうのを使うグラフ問題。そういえばグラフ問題は初めてだった気がする。概念はわかったし、手作業で書き込んでいけと言われるとできるけど、コードに起こせない。キューを参照しながらループの中でキューに値を追加していくってのがむずい。ただ、こういうコードを１行ごとに値確認しながら動かすのは結構面白い。10回ぐらい同系統の問題でて慣れれば、回答できるんじゃないだろうか。

コード

N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]
for a,b in AB:
 to_list[a - 1].append(b - 1)
 to_list[b - 1].append(a - 1)
marked = {0}
que = [0]
for i in que:
   for j in to_list[i]:
       if j in marked: continue
       que.append(j)
       marked.add(j)
       prev[j] = i+1
print('Yes')
print(*prev[1:], sep='\n')

ちなみに、markedをリストで実装したらTLEだった。検索は辞書の方が早い。というのはどっかで聞いてたけど忘れてた。