Lunghezza del percorso più breve con BFS

Poiché l’algoritmo BFS parte da un nodo e si espande gradualmente visitando i vicini, è possibile trovare il percorso più breve dal nodo iniziale a tutti gli altri nodi del grafo. Per ottenere questo risultato, occorre apportare una piccola modifica all’algoritmo di base. Introdurremo un array delle distanze d, inizialmente impostato tutto a -1. Se il valore in d di un vertice è -1, significa che quel vertice non è stato ancora visitato. Se invece è un valore positivo, indica la distanza del vertice corrente dal nodo iniziale:

from collections import deque

n, e = map(int, input().split())        # n: vertici, e: archi
g = [[] for _ in range(n)]              # grafo - lista di adiacenza

for _ in range(e):                      # lettura degli archi
    a, b = map(int, input().split())    # a -> b e b -> a
    g[a].append(b)
    g[b].append(a)

start = int(input())                    # vertice di partenza
d = [-1] * n                            # distanza dal vertice di partenza
q = deque([start])                      # coda di vertici
d[start] = 0                            # distanza dal vertice di partenza a se stesso è 0

while q:                                # finché la coda non è vuota
    v = q.popleft()                     # estrai un vertice dalla coda
    print(v, end=' ')                   # stampa il vertice
    for to in g[v]:                     # per ciascun vertice collegato a v
        if d[to] == -1:                 # se il vertice non è ancora visitato
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            q.append(to)                # aggiungi il vertice alla coda

print(d)

In questo esempio, inizializziamo d con -1, in modo da indicare che nessun vertice è stato ancora visitato. Quindi impostiamo d[start] a 0, il che significa che la distanza tra il vertice start e se stesso è 0.

Man mano che l’algoritmo elabora i nodi, i relativi valori nell’array d vengono aggiornati, fornendo la distanza di ogni nodo dal vertice start.

Osserviamo il funzionamento dell’algoritmo su alcuni input di esempio:

Sfida: Trovare la lunghezza del percorso più breve

Dato un grafo non orientato con v vertici e e archi, si richiede di calcolare la lunghezza del percorso più breve tra il vertice 1 e il vertice v. Se non esiste un collegamento tra di loro, il programma deve stampare Impossible.

Input

La prima riga di input contiene due interi v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).

Le successive e righe contengono una coppia di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.

Output

Il programma deve stampare la lunghezza del percorso più breve tra 1 e v.

Esempi