Module: BFS - Caminata de amplitud


Problem

1/6

BFS: Principio (C++)

Theory Click to read/hide

Búsqueda primero en amplitud (BFS)
BFS (búsqueda primero en amplitud, búsqueda primero en amplitud) - un método transversal de gráfico, usado muy a menudo en algoritmos simples y avanzados. La búsqueda primero en amplitud funciona recorriendo los niveles individuales del gráfico, comenzando en el nodo de origen y alejándose gradualmente de él. Esto se muestra claramente en la animación.
Para escribir el BFS  más simple, debe poder trabajar con una estructura de datos que le permita tomar desde el principio y ponerlo hasta el final, y también poder almacenar el gráfico en forma de lista de adyacencia (es decir, con una cola).
 
Descripción formal del algoritmo
1) Coloque el número del vértice desde el que comienza la búsqueda en la cola inicialmente vacía.
2) Extraiga el vértice U del principio de la cola y márquelo como usado en una matriz separada.
3) Al final de la cola, agregar todos los vértices que podamos alcanzar usando el borde del vértice U, y que aún no estén etiquetados.
4) Si la cola está vacía, entonces se escanearon todos los nodos del gráfico conectado; de lo contrario, regrese al paso 2.
 
Complejidad
Dado que el algoritmo visita todos los nodos del gráfico en el peor de los casos, al almacenar el gráfico como listas de adyacencia, la complejidad temporal del algoritmo es O(|V| + |E|) , donde V es el conjunto de vértices del gráfico y E es el conjunto de aristas. En otras palabras, el algoritmo funciona en el peor de los casos para number de aristas + número de vértices.

 

Problem

Algunas aldeas están conectadas por carreteras, que se pueden representar como un gráfico sin dirección. Los vértices de este gráfico son pueblos, y los bordes son caminos entre pueblos (el gráfico puede contener ciclos). Se sabe que en el pueblo S un artel Buhoneros. Todas las mañanas, para vender su pequeña mercería, los buhoneros acuden a pueblos que todavía no han visitado, y a los que hay un camino desde el actual. El artel de los vendedores ambulantes siempre se divide en grupos para que puedan dar la vuelta a todos los pueblos que tienen caminos desde el actual en un día.
¿En cuántos días los vendedores ambulantes visitarán todos los pueblos? Escribe una función BFS que devolverá la respuesta a la tarea.

 
Entrada
La primera línea contiene 3 enteros n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - el número de pueblos, el número de caminos entre ellos y el número del pueblo en el que se encuentra la pandilla del vendedor ambulante.  ;En las siguientes líneas m< /code> contienen 2 números, cada u, v(\(1 < = u, v <= n\ )) - números de dos pueblos entre los cuales hay una carretera. Los pueblos están indexados con 1.

Impresión
Imprima un solo número: cuántos días tardarán los vendedores ambulantes en visitar todos los pueblos.

 

Ejemplos

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++
# Entrada Salida
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
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!