Pythonで競プロしてる 
N個の部屋とM本の通路がある洞窟の、それぞれの部屋に配置する道しるべの置き方を求める問題です。
from collections import deque
n, m = map(int, input().split())
ab = [[] for i in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
ab[a].append(b)
ab[b].append(a)
ans = [-1]*(n+1)
que = deque([1])
while que:
q = que.popleft()
for i in ab[q]:
if ans[i] == -1:
que.append(i)
ans[i] = q
print("Yes")
for i in range(2,n+1):
print(ans[i])BFS（幅優先探索）を用いて解くのですが、その説明は他のサイトにお任せして、今回のコードでどのような処理をしたかを説明します。
まず、abというリストを作成して、辺で繋がっているa,b同士を代入します。
入力例１の場合、for文の後にabを出力すると、
ab = [[], [2], [1, 3, 4], [2, 4], [3, 2]]というリストになっています。
ab[1] = [2]
ab[2] = [1,3,4]ですね。1は2と繋がっており、2は、1,3,4と繋がっていることがを入力から代入したためです。
次に最後に出力する答えのリスト「ans」の「n+1」個の要素に「-1」を代入します。
今回は、collectionsモジュールの「deque」を使用します。
これを使うことで、先頭の要素を取得・削除する際に、時間コストを少なくすることができます。
que = deque([1])というリストを作っておいて、先頭の文字列を取得・削除（popleft()を使用）します。
以下の部分のコードを見てください。
while que:
q = que.popleft()
for i in ab[q]:
if ans[i] == -1:
que.append(i)
ans[i] = qque.popleft() の最初の取得は1です。
ab[1]には[2]が入っており、ans[2] = -1 です。
ですので、queの最後に2を加え、ans[2]に「1」を代入しています。
次の取得は2です。
ab[2]には [1,3,4]が入っているため、一つずつ判定します。
ans[1]に2が代入されてしまいますが、出力には関係ないので無視します。
ans[3] , ans[4]に2を代入します。
ここで、queには[1,3,4]が入っています。
その次の取得は再び1ですが、ans[2] = 1 であるため、何も変化せず終わります。
3,4 に関しても同様に変化せず、新しい要素がqueに加わるわけではないので、空リストになり、ループから抜け出します。
このとき「ans」は、
ans = [-1, 2, 1, 2, 2]であるので、3つ目の要素から順番に出力します。
その前に「Yes」を出力するのを忘れないように。今回、答えが「No」になるパターンは存在しないため、場合わけは不要です。
とても分かりやすい良心的な記事を、ありがとうございます。
コードの詳細な説明が充実していて、大変、勉強になります。
自分は、やっと茶色になったばかりです。10か月掛かりました(笑)
Dは ほとんど解けません。解説して頂いた記事を読んで、
「どうしたら、この解法を思いつくのだろう」と不思議に思う
ことがあります。その辺も、教えて頂ければ助かります。
今後とも、よろしく、お願いします。感謝しています。
追伸：最短経路の長さを求めないBFS、面白いですね。
上の方と同じく、具体的でわかりやすい解説だと思いました。
慣れている人だとコードを読めば処理内容が自然に想像できるのかもしれませんが、茶帯の自分にはちょっと脳への負荷が大きくて……(笑)
参考にさせていただきます。