< style="text-align: center">Sesja
na dół
BFS
Dany jest graf o m krawędziach. Dla każdego wierzhołka wypisz jego odległość od wierzchołka numer 0.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowite m (0 ≤ m ≤ 10^6) oznaczającą liczbę krawędzi grafu zakończoną znakiem nowej linii. Wierzchołki są ponumerowane od 0 do n. W (i + 1)-szym wierszu wejścia znajduje się opis i-tej krawędzi; zawiera on liczby vi oraz ui (1 ≤ vi, ui ≤ n) oznaczające, że i-ta krawędź łączy wierzchołki vi oraz ui. Każda para wierzchołków jest połączona co najwyżej jedną krawędzią.

Wyjście

Wyjście składa się z n liczb d1, d2, ..., dn oddzielonych pojedynczymi spacjami, z których i-ta oznacza odległość wierzchołka numer i od wierzchołka numer 0. Jeżeli nie istnieje droga między wierzchołkiem numer 0 i wierzchołkiem numer i, Twój program powinien wypisać −1.
Przykład
Wejście:
5
0 1
5 3
0 3 
2 4
1 3
Wyjście:
0 1 -1 1 -1 2
Wskazówka:
Nie korzystaj z pythonowych bibliotek grafowych. 
Najprościej można użyć słownika i listy jako stosu.
# tworzymy graf jako słownik list sąsiedztwa
graph = {}
edges = int(input()) # wczytujemy liczbę krawędzi
for i in range(edges): # dla każdej krawędzi
    u,v = input().split()
    if u not in graph: # jeśli u nie ma w grafie
        graph[u] = [] # tworzymy dla niego pustą listę sąsiadów
    if v not in graph: # jeśli v nie ma w grafie
        graph[v] = [] # tworzymy dla niego pustą listę sąsiadów

    graph[u].append(v) # dodajemy v do listy sąsiadów u
    graph[v].append(u) # dodajemy u do listy sąsiadów v 
Teraz wystarczy zaimplementować metodę BFS i w dodatkowej liście podczas odwiedzania wierzchołków zapisywać odległości wierzchołków od 0.


Rozwiązanych zadań 0:

Powrót do zadań

engine by marwoj