[Python] BFS (recherche de priorité de largeur) ABC168D

ABC168D

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

[Python] BFS (recherche de priorité de largeur) ABC168D
Algorithme en Python (recherche de priorité de largeur, bfs)
Exercice Python Recherche prioritaire sur 1 largeur
[Python] Recherche de bisection ABC155D
Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)
[Python] DFS (recherche de priorité en profondeur) ABC157D
[Python] Recherche de priorité de profondeur et recherche de priorité de largeur
[Python] ABC175D
Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python
Recherche de priorité de largeur (BPF) Peut-être compris (python)
[Python] DP ABC184D
[Python] UnionFind ABC177D
Résoudre ABC168D en Python
Recherche séquentielle avec Python
Résolvez ABC167-D avec Python
[Python] Recherche (itertools) ABC167C
Dichotomie avec Python
[Python] Recherche (NumPy) ABC165C
Recherche de bisection (python2.7) mémo
Résoudre ABC159-D en Python
recherche complète de bits python
Recherche linéaire en Python
Dichotomie avec python
Dichotomie avec Python 3
Rechercher sur Twitter avec Python
Recherche binaire en Python
[Python] Somme cumulée ABC179D
J'ai essayé d'implémenter la recherche de priorité de largeur avec python (file d'attente, dessin personnalisé)
Résolution avec Ruby et Python AtCoder ABC151 D Recherche de priorité de largeur
Algorithme de recherche utilisant word2vec [python]
Homebrew Python - Programme de recherche YouTube
[Python] DFS (recherche de priorité en profondeur) ATC001A
Recherche binaire en Python / C ++
Algorithme en Python (dichotomie)
Recherche de bits complète avec Python
Trouver le diamètre du graphique par recherche de priorité de largeur (mémoire Python)
Les moteurs de recherche fonctionnent avec python
Rechercher des tweets Twitter avec Python
Rationalisez la recherche Web avec Python
Ecrire une dichotomie en Python
[Python] Comment dériver nCk (ABC156-D)
Algorithme en Python (recherche de priorité en profondeur, dfs)
Maîtrisez la recherche linéaire! ~ Version d'implémentation Python ~
Écrire une recherche de priorité en profondeur en Python
(Python) ABC162-D Journal de discussion et solution
Reproduire la recherche à une touche avec Python 3.7.3. (Windows 10)
Recherche de priorité de profondeur à l'aide de la pile en Python
Recherche de 2 minutes Python et ses dérivés
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
Résolution avec Ruby, Perl, Java et Python AtCoder AGC 033 A Recherche de priorité de largeur