Study

Profile

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

Задача 38792. BFS: Beginning (Python)


Задача

Темы: Обход в ширину
Some villages are connected by roads, which can be represented as an undirected graph. The vertices of this graph are villages, and the edges are roads between villages (the graph may contain cycles). It is known that in the village S an artel Pedlars. Every morning, to sell their small haberdashery, peddlers go to villages that have not yet visited, and to which there there is a road from the current one. The artel of peddlers is always divided into groups so that they can go around all the villages that have roads from the current one in one day.
In how many days will the peddlers visit all the villages? Write a \(bfs()\) function that will return the answer to the problem.


Input
The first line contains 3 integers n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - the number of villages, the number of roads between them, and the number of the village in which the peddler's gang is based. In the following m< /code> lines contain 2 numbers each u, v(\(1 <= u, v <= n\ )) - numbers of two villages between which there is a road. Villages are indexed with 1.

Imprint
Print a single number - how many days it will take the pedlars to visit all the villages.
 
 
Examples
# Input Output
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4

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

Комментарий учителя

Ваш ответ

Python
Напишите программу ниже 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
vector<bool> used;//used[i] = true, если мы были в вершине i
vector<vector<int> > g;//список смежности
vector<int> tm;//tm[i] - день, когда подожглась деревня i
int n, m, s;


int bfs()
{  
}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
        return 0;
}
     

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