Олимпиадный тренинг

Задача . BFS: Начало (Python)


Задача

Темы: Обход в ширину
Некоторые деревни соединены между собой дорогами, которые можно представить в виде неориентированного графа. Вершины данного графа - это деревни, а ребра - дороги между деревнями (граф может содержать циклы). Известно, что в деревне S основана артель коробейников. Каждое утро, чтобы продать свою мелкую галантерею, коробейники выходят в деревни, которые еще не посетили, и в которые есть дорога из текущей. Артель коробейников всегда делится на группы так, чтобы они могли за один день обойти все деревни, которые имеют дороги из текущей.
За сколько дней коробейники посетят все деревни?
Напишите функцию \(bfs()\), которая будет возвращать ответ на задачу.


Входные данные
В первой строке вводятся 3 целых числа n, m, s (\(1 <= n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - количество деревень, количество дорог между ними и номер деревни, в которой основана артель коробейников. В следующих m строках содержится по 2 числа u, v(\(1 <= u, v <= n\)) - номера двух деревень, между которыми есть дорога. Индексация деревень ведется с 1.

Выходные данные
Выведите одно число - за сколько дней коробейники посетят все деревни.
 
 
Примеры
№ Входные данные Выходные данные
1 6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6		 4

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python477
Комментарий учителя

Ваш ответ

Python
Напишите программу ниже 
def bfs():                 
n, m, s = map(int, input().split())
s  -=  1
visited = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())
     

Загруженные файлы
Нет