Module: BFS - Caminata de amplitud


Problem

2/6

BFS: Principio (Python)

Theory Click to read/hide

BFS (búsqueda primero en amplitud) es un método de recorrido de gráficos, que se usa con mucha frecuencia 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 un BFS simple, debe poder trabajar con una cola, una estructura de datos que le permita tomar desde el principio y ponerlo hasta el final, y también poder almacenar un gráfico en el formulario de una lista de adyacencia.
 
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 podemos alcanzar usando el borde del vértice U y que aún no están marcados.
4) Si la cola está vacía, entonces se escanearon todos los nodos del gráfico conectado; de lo contrario, regrese al paso 2.
 
Dificultad de trabajo
Dado que, en el peor de los casos, el algoritmo visita todos los nodos del grafo, al almacenar el grafo en forma de listas de adyacencia, la complejidad temporal del algoritmo es O(|V| + |E|), donde V es el conjunto de vértices del grafo, y E es el conjunto de aristas.  ;
En otras palabras, el algoritmo funciona en el peor de los casos para el número de aristas + el 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? Escriba una función \(bfs()\) que devuelva la respuesta al problema.


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
Python
# Entrada Salida
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
Write the program below 
def bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

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