Module: BFS - Breadth Walk


Problem

2/6

BFS: Beginning (Python)

Theory Click to read/hide

BFS (breadth-first search) is a graph traversal method, very often used in both simple and advanced algorithms. Breadth-First Search works by stepping through the individual levels of the graph, starting at the source node and gradually moving away from it. This is clearly shown in the animation.

To write a simple BFS, you need to be able to work with a queue, a data structure that allows you to take from the beginning and put it to the end, and also be able to store a graph in the form of an adjacency list.
 
Formal description of the algorithm
1) Place the number of the vertex from which the search begins into the initially empty queue.
2) Extract vertex U from the beginning of the queue and mark it as used in a separate array.
3) At the end of the queue, add all the vertices that we can reach using the edge from the vertex U and that are not marked yet.
4) If the queue is empty, then all nodes of the connected graph have been scanned, otherwise return to step 2.
 
Difficulty of work
Since, in the worst case, the algorithm visits all nodes of the graph, when storing the graph in the form of adjacency lists, the time complexity of the algorithm is O(|V| + |E|), where V is the set of vertices of the graph, and E is the set of edges.  ;
In other words, the algorithm works in the worst case for the number of edges + the number of vertices.

 

Problem

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
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
#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;
}

     

Program check result

To check the solution of the problem, you need to register or log in!