[Python] BFS (breadth-first search) ABC168D

from collections import deque

#Number of vertices and sides
N, M = map(int, input().split())
#Edge
AB = [map(int, input().split()) for _ in range(M)]

#Adjacency list settings for undirected graphs
link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)
    
#BFS data frame
dist = [-1] * (N + 1)  #No sign set
que = deque([1])       #Visit queue starting from vertex 1

#BFS start(Search until the queue is empty)
while que:
    v = que.popleft() #First vertex from queue(Current location)v get
    
    for i in link[v]:
      #Set a sign to the current location at the unset vertex i and add it to the visit queue
      if dist[i] == -1:
        dist[i] = v
        que.append(i)

#Result output (signboard installed at each vertex)
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Recommended Posts