[Python] [BFS] Au concours de codeur pour débutants 168-D [.. Double Dots]

• Ceci est un mémorandum personnel qui résume comment implémenter les algorithmes qui apparaissent dans la programmation de la compétition.

Énoncé du problème (.. Double Dots)

ABC168-D Double Dots

Il y a une grotte quelque part. La grotte a N chambres et M passages, les chambres sont numérotées de 1 à N et les passages sont numérotés de 1 à M. Le passage i relie la salle Ai et la salle Bi dans les deux sens. Vous pouvez faire des allers-retours entre les deux salles par plusieurs passages. La chambre 1 est une pièce spéciale avec une entrée de grotte. Comme l'intérieur de la grotte est sombre, j'ai décidé de fournir un guide pour chaque pièce autre que la pièce 1. Le sentier de chaque pièce doit pointer vers l'une des pièces qui est directement reliée à cette pièce par une passerelle. Étant donné que l'intérieur de la grotte est dangereux, l'objectif est de remplir les conditions suivantes pour toutes les pièces sauf la salle 1. Si vous partez de cette pièce et répétez "regardez le panneau de signalisation dans la pièce dans laquelle vous vous trouvez et passez à la pièce vers laquelle il pointe", Accédez à la salle 1 avec le moins de coups. Déterminez s'il existe un arrangement de sentiers qui peut atteindre votre objectif et, le cas échéant, créez un tel arrangement.

répondre

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):
    #Créer un graphique
    g = creategraph(n,l)
    #NG s'il y a une pièce séparée
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    #Créer un guide avec BFS
    navi = bfs(n,g)
    #NG si la consigne de la pièce sauf la salle 1 n'est pas mise à jour
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)
    
#Recherche de priorité de largeur BFS
def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        #Prenez votre position actuelle dans la file d'attente
        cp = q.popleft()
        #Obtenez une liste des points adjacents à votre emplacement actuel
        np = g[cp]
        #Si le point adjacent n'est pas recherché, placez-le dans la file d'attente + mettez à jour le repère
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi
    
#Générer une liste qui contient les contiguïtés de chaque nœud
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()