Module: BFS - Breadth Walk


Problem

1/6

BFS: Beginning (C++)

Theory Click to read/hide

Breadth First Search (BFS)
BFS (breadth-first search, breadth-first search) - 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 the simplest BFS , you need to be able to work with a data structure that allows you to take from the beginning and put it to the end, and also be able to store the graph in the form of an adjacency list (i.e. with a queue ).
 
Formal description of the algorithm
1) Place the number of the vertex from which the search begins into the initially empty queue.
2) Extract the 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 which we can reach using the edge from the vertex U, and which are not yet labeled.
4) If the queue is empty, then all nodes of the connected graph have been scanned, otherwise return to step 2.
 
Complexity
Since the algorithm visits all nodes of the graph in the worst case, when storing the graph as adjacency lists, time complexity of the algorithm is O(|V| + |E|), where V is the set of graph vertices, and E is the set of edges. In other words, the algorithm works in the worst case for number of edges + 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 task.

 
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
C++
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!