Je n'ai pas pu le résoudre à ABC hier et je ne pouvais pas dormir la nuit, alors je vais le revoir.
** Pensées ** En raison de restrictions, les graphiques donnés sont concaténés car il est possible de se déplacer entre les pièces en utilisant plusieurs routes. S'il s'agit d'un graphe concaténé, il ressemblera toujours à une construction. Si vous le soumettez avec print ('Non'), ce sera 0AC. La solution est de rechercher le guide à partir de 1 à la même profondeur, et lorsque vous atteignez une pièce plus profonde que vous, placez le guide dans votre pièce. C'est facile à mettre en œuvre avec BFS.
ver est une liste de salles accessibles depuis ver [i] en une seule fois
from collections import deque
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
q = deque([])
path = [-1] * n
ver = [[] for _ in range(n)]
for i in range(m):
ab[i].sort()
if ab[i][0] == 1:
q.append([ab[i][0]-1,ab[i][1]-1])
#path[ab[i][1]-1] = 1
ver[ab[i][0]-1].append(ab[i][1]-1)
ver[ab[i][1]-1].append(ab[i][0]-1)
def bfs(q, visited_list):
while len(q) > 0:
now = q.popleft()
go = now[1]
if visited_list[go] == -1:
visited_list[go] = now[0]+1
for i in range(len(ver[go])):
q.append([go,ver[go][i]])
return visited_list
ans = bfs(q,path)
print('Yes')
for i in range(1,n):
print(ans[i])
Le montant du calcul est de O $ (N + M) $
C'était un problème très fondamental. Hier, j'avais l'impression de tourner, alors je ferai de mon mieux pour en terminer un lors du prochain AGC. à plus.
Les problèmes de graphes sont faciles à penser en utilisant this.
Recommended Posts