ABC169 問題D [asarenメモ] #幅優先(BFS)基本

Atcoder Begginer Contest 169 でのキューを使った幅優先探索のメモ

atcoder.jp

import os, sys, re, math
from collections import deque

N,M = map(int, input().split(' '))

tag = [-1] * N
path_r = {}

for _ in range(M):
    A,B = map(lambda x: int(x) - 1, input().split(' '))
    if A in path_r:
        path_r[A].append(B)
    else:
        path_r[A] = [B]
    if B in path_r:
        path_r[B].append(A)
    else:
        path_r[B] = [A]

tag[0] = 0
queue = deque()
queue.append(0)

while queue:
    next_r = queue.popleft()
    for t in path_r[next_r]:
        if tag[t] < 0:
            tag[t] = next_r
            queue.append(t)

if -1 in tag:
    print('No')
else:
    print('Yes')
    for t in tag[1:]:
        print(t+1)

※asarenとは自主的な競技プログラミング練習会のことです