Notez que puisqu'il s'agit d'un graphe concaténé, le minimum est garanti par le principe de BFS.
référence BFS (Width Priority Search) Super Introduction! ~ Utilisez la file d'attente de façon vivante ~
Exemple de code
from collections import deque
#Nombre de sommets et de côtés
N, M = map(int, input().split())
#Côté
AB = [map(int, input().split()) for _ in range(M)]
#Paramètre de liste adjacente pour le graphique non dirigé
link = [[] for _ in range(N + 1)]
for a, b in AB:
link[a].append(b)
link[b].append(a)
#Trame de données BFS
dist = [-1] * (N + 1) #Aucun signe défini
que = deque([1]) #Visite de la file d'attente à partir du sommet 1
#Début de BFS(Rechercher jusqu'à ce que la file d'attente soit vide)
while que:
v = que.popleft() #Premier pic de la file d'attente(Localisation actuelle)v obtenir
for i in link[v]:
#Définissez un signe sur l'emplacement actuel au sommet i non défini et ajoutez-le à la file d'attente de visite
if dist[i] == -1:
dist[i] = v
que.append(i)
#Sortie de résultat (signature installée à chaque sommet)
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))
Recommended Posts