Module: BFS - Marche de la largeur


Problem

1/6

BFS : Débutant (C++)

Theory Click to read/hide

Recherche étendue d'abord (BFS)
BFS (recherche en largeur d'abord,recherche en largeur d'abord) - une méthode de parcours de graphe, très souvent utilisée dans les algorithmes simples et avancés. La recherche étendue d'abord fonctionne en parcourant les niveaux individuels du graphique, en commençant par le nœud source et en s'en éloignant progressivement. Ceci est clairement montré dans l'animation.
Pour écrire le BFS  le plus simple, vous devez être capable de travailler avec une structure de données qui vous permet de prendre depuis le début et de le mettre à la fin, et aussi de pouvoir stocker le graphe sous la forme d'une liste d'adjacence (c'est-à-dire avec une file d'attente).
 
Description formelle de l'algorithme
1) Placer le numéro du sommet à partir duquel la recherche commence dans la file d'attente initialement vide.
2) Extrayez le sommet U du début de la file d'attente et marquez-le comme utilisé dans un tableau séparé.
3) En fin de file, ajouter tous les sommets que l'on peut atteindre par l'arête du sommet U, et qui ne sont pas encore étiquetés.
4) Si la file d'attente est vide, alors tous les nœuds du graphe connexe ont été scannés, sinon retournez à l'étape 2.
 
Complexité
Étant donné que l'algorithme visite tous les nœuds du graphe dans le pire des cas, lors du stockage du graphe sous forme de listes de contiguïté, la complexité temporelle de l'algorithme est O(|V| + |E|) , où V est l'ensemble des sommets du graphe et E est l'ensemble des arêtes. En d'autres termes, l'algorithme fonctionne dans le pire des cas pour nombre d'arêtes + nombre de sommets.

 

Problem

Certains villages sont reliés par des routes, qui peuvent être représentées sous la forme d'un graphe non orienté. Les sommets de ce graphe sont des villages, et les arêtes sont des routes entre villages (le graphe peut contenir des cycles). On sait que dans le village S un artel Colporteurs. Tous les matins, pour vendre leur petite mercerie, les colporteurs se rendent dans des villages qu'ils n'ont pas encore visités, et auxquels il existe une route depuis l'actuel. L'artel des colporteurs est toujours divisé en groupes afin qu'ils puissent faire le tour de tous les villages qui ont des routes depuis l'actuel en une journée.
Dans combien de jours les colporteurs visiteront-ils tous les villages ? Écrivez une fonction BFS qui renverra la réponse à la tâche.

 
Entrée
La première ligne contient 3 entiers n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - le nombre de villages, le nombre de routes entre eux et le numéro du village dans lequel le gang de colporteurs est basé.  ;Dans les lignes m suivantes contiennent 2 nombres chacun u, v(\(1 < = u, v <= n\ )) - numéros de deux villages entre lesquels il y a une route. Les villages sont indexés avec 1.

Mentions légales
Imprimez un seul chiffre - combien de jours il faudra aux colporteurs pour visiter tous les villages.

 

Exemples
# Entrée Sortie
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!