Ich konnte es gestern bei ABC nicht lösen und ich konnte nachts nicht schlafen, also werde ich es überprüfen.
** Gedanken ** Aufgrund von Einschränkungen werden die angegebenen Grafiken verkettet, da zwischen mehreren Straßen zwischen Räumen gewechselt werden kann. Wenn es sich um ein verkettetes Diagramm handelt, sieht es immer wie eine Konstruktion aus. Wenn Sie es mit Druck ('Nein') einreichen, ist es 0AC. Die Lösung besteht darin, die Führung von 1 in derselben Tiefe zu durchsuchen. Wenn Sie einen Raum erreichen, der tiefer als Sie ist, platzieren Sie die Führung in Ihrem Raum. Dies ist mit BFS einfach zu implementieren.
ver ist eine Liste von Räumen, die von ver [i] auf einmal erreicht werden können
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])
Der Berechnungsbetrag beträgt $ O (N + M) $
Es war ein sehr grundlegendes Problem. Gestern hatte ich das Gefühl, ich würde mich drehen, also werde ich mein Bestes geben, um einen bei der nächsten AGC zu absolvieren. wir sehen uns.
Bei der Verwendung von this kann man sich Grafikprobleme leicht vorstellen.
Recommended Posts