【Python】【BFS】AtCoder Beginner Contest 168-D [.. Double Dots]

※競技プログラミングででてくるアルゴリズムの実装方法をまとめる自分用備忘録です。

#問題文　(.. Double Dots)

ABC168-D Double Dots

あるところに、洞窟があります。
洞窟にはN個の部屋とM本の通路があり、部屋には1からNの、通路には1からMの番号がついています。
通路iは部屋Aiと部屋Biを双方向につないでいます。どの2部屋間も、通路をいくつか通って行き来できます。
部屋1は洞窟の入り口がある特別な部屋です。
洞窟の中は薄暗いので、部屋1以外の各部屋に1つずつ道しるべを設けることにしました。
各部屋の道しるべは、その部屋と通路で直接つながっている部屋の1つを指すように置きます。
洞窟の中は危険なので、部屋1以外のどの部屋についても以下の条件を満たすことが目標です。
その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、
部屋1に最小の移動回数でたどり着く。
目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を1つ出力してください。

#解答

from collections import deque

mi = lambda:list(map(int,input().split()))
mix = lambda x:list(mi() for _ in range(x))
##########
def main(n,m,l):
    #グラフの作成
    g = creategraph(n,l)
    #独立した部屋がある場合はNG
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    #BFSで道標を作成
    navi = bfs(n,g)
    #部屋1を除く部屋の道標が更新されていなければNG
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)
    
#BFS幅優先探索
def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        #キューから現在地を取り出す
        cp = q.popleft()
        #現在地の隣接点リストを取得
        np = g[cp]
        #隣接点が未探索ならキューに入れる＋道標更新
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi
    
#各Nodeの隣接点を保持するリストを生成する
def creategraph(n,l):
    g = {i:[] for i in range(n+1)}
    for a,b in l:
        g[a].append(b)
        g[b].append(a)
    return g

def resolve():
    n,m = mi()
    l = mix(m)
    main(n,m,l)

if __name__ == "__main__":
    resolve()