Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 32 Mb

Ответы на вопросы

Задача: BFS

Дан связный неориентированный граф, в котором вершины - деревни, а ребра - дороги между деревнями(могут быть циклы).
Известно, что в деревне S случился пожар, каждое утро загораются все деревни, которые еще не горят и у которых есть дорога в горящую деревню.
Вас просят сказать за сколько дней сгорят все деревни. Напишите функцию БФСа, которая будет возвращать ответ на задачу.
В первой строке вводятся 3 целых числа n, m, k(1 <= n <= 10^5, 0 <= m <= 10^5, 1 <= k <= n) - количество деревней, количество дорог между ними и номер деревни, в которой случился пожар.
В следующих m строках содержится по 2 числа u, v(1 <= u, v <= n) - номера двух деревень между которыми есть дорога. Индексация деревень ведется с 1.
Выведите одно число - за сколько дней сгорят все деревни.
Пример
Ввод:
6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6
Вывод
4

C++
Напишите программу ниже
#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;
}  
           

Ваш ответ:

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


Нет

Примечание учителя: