[Python] [BFS] Beim Coder-Anfängerwettbewerb 168-D [.. Double Dots]

• Dies ist ein persönliches Memorandum, in dem zusammengefasst wird, wie die in der Wettbewerbsprogrammierung enthaltenen Algorithmen implementiert werden.

Problemstellung (.. Double Dots)

ABC168-D Double Dots

Irgendwo gibt es eine Höhle. Die Höhle hat N Räume und M Durchgänge, die Räume sind von 1 bis N und die Durchgänge von 1 bis M nummeriert. Passage I verbindet Raum Ai und Raum Bi in beide Richtungen. Sie können zwischen den beiden Räumen durch mehrere Passagen hin und her gehen. Raum 1 ist ein spezieller Raum mit Höhleneingang. Da das Innere der Höhle dunkel ist, habe ich beschlossen, für jeden Raum außer Raum 1 einen Führer bereitzustellen. Der Pfad für jeden Raum sollte auf einen der Räume zeigen, der durch einen Gehweg direkt mit diesem Raum verbunden ist. Da das Innere der Höhle gefährlich ist, besteht das Ziel darin, die folgenden Bedingungen für alle Räume außer Raum 1 zu erfüllen. Wenn Sie von diesem Raum aus beginnen und wiederholen: "Sehen Sie sich das Straßenschild in dem Raum an, in dem Sie sich befinden, und gehen Sie zu dem Raum, auf den es zeigt". Gehe mit der geringsten Anzahl von Zügen zu Raum 1. Bestimmen Sie, ob es eine Anordnung von Pfaden gibt, mit denen Sie Ihr Ziel erreichen können, und geben Sie in diesem Fall eine solche Anordnung aus.

Antworten

from collections import deque

mi = lambda:list(map(int,input().split()))
mix = lambda x:list(mi() for _ in range(x))
##########
def main(n,m,l):
    #Erstellen eines Diagramms
    g = creategraph(n,l)
    #NG, wenn es einen separaten Raum gibt
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    #Erstellen Sie einen Leitfaden mit BFS
    navi = bfs(n,g)
    #NG, wenn die Richtlinie des Raums mit Ausnahme von Raum 1 nicht aktualisiert wird
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)
    
#Suche nach BFS-Breitenpriorität
def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        #Nehmen Sie Ihren aktuellen Standort aus der Warteschlange
        cp = q.popleft()
        #Holen Sie sich eine Liste benachbarter Punkte an Ihrem aktuellen Standort
        np = g[cp]
        #Wenn der benachbarte Punkt nicht durchsucht wird, stellen Sie ihn in die Warteschlange und aktualisieren Sie die Richtlinie
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi
    
#
def creategraph(n,l):
    g = {i:[] for i in range(n+1)}
    for a,b in l:
        g[a].append(b)
        g[b].append(a)
    return g

def resolve():
    n,m = mi()
    l = mix(m)
    main(n,m,l)

if __name__ == "__main__":
    resolve()