Module: BFS - Caminhada em Largura


Problem

1/6

BFS: Iniciando (C++)

Theory Click to read/hide

Breadth First Search (BFS)
BFS (breadth-first search, width-first search) - um método de travessia de grafo, muito frequentemente usado em algoritmos simples e avançados. A busca em largura funciona percorrendo os níveis individuais do gráfico, começando no nó de origem e gradualmente se afastando dele. Isso fica claro na animação.
Para escrever o BFS  mais simples, você precisa ser capaz de trabalhar com uma estrutura de dados que permita pegar do início e colocá-lo no final e também ser capaz de armazenar o grafo na forma de uma lista de adjacência (ou seja, com uma fila ).
 
Descrição formal do algoritmo
1) Coloque o número do vértice a partir do qual a busca começa na fila inicialmente vazia.
2) Extraia o vértice U do início da fila e marque-o como usado em um array separado.
3) No final da fila, adicione todos os vértices que podemos alcançar usando a aresta do vértice U, e que ainda não estão rotulados.
4) Se a fila estiver vazia, todos os nós do grafo conectado foram verificados, caso contrário, retorne ao passo 2.
 
Complexidade
Como o algoritmo visita todos os nós do grafo no pior caso, ao armazenar o grafo como listas de adjacência, a complexidade de tempo do algoritmo é O(|V| + |E|) , onde V é o conjunto de vértices do gráfico e E é o conjunto de arestas. Em outras palavras, o algoritmo funciona no pior caso para number de arestas + número de vértices.

 

Problem

Algumas aldeias são conectadas por estradas, que podem ser representadas como um gráfico não direcionado. Os vértices deste grafo são aldeias e as arestas são estradas entre aldeias (o grafo pode conter ciclos). Sabe-se que na aldeia S um artel Vagadistas. Todas as manhãs, para venderem os seus pequenos armarinhos, os mascates dirigem-se a aldeias que ainda não visitaram, e para as quais existe uma estrada a partir da atual. O artel dos mascates está sempre dividido em grupos para que possam percorrer num dia todas as aldeias que têm estradas a partir da actual.
Em quantos dias os mascates visitarão todas as aldeias? Escreva uma função BFS que retornará a resposta para a tarefa.

 
Entrada
A primeira linha contém 3 inteiros n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - o número de aldeias, o número de estradas entre elas e o número da aldeia em que se baseia a quadrilha do mascate.  ;Nos seguintes m< /code> as linhas contêm 2 números cada u, v(\(1 < = u, v <= n\ )) - números de duas aldeias entre as quais existe uma estrada. As aldeias são indexadas com 1.

Impressão
Imprima um único número - quantos dias os mascates levarão para visitar todas as aldeias.

 

Exemplos
# Entrada Saída
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!