Module: BFS - Umgehung in der Breite


Problem

2/6

BFS: Anfang (Python)

Theory Click to read/hide

BFS (Erkennung in Breite, Breite-erste Suche) ist eine Möglichkeit, die Zählung zu umgehen, sehr oft sowohl in einfachen Algorithmen als auch in fortgeschrittenen angewendet. Die Suche in der Breite ist ein Mittel, die einzelnen Ebenen des Diagramms nacheinander zu überprüfen, beginnend mit dem Knoten der Herkunft, und allmählich zu entfernen. Es ist klar auf Animation.

Um ein einfaches BFS zu schreiben, ist es notwendig, mit einer Zeile arbeiten zu können, eine Datenstruktur, die es von Anfang und Ende nehmen lässt und den Graph als eine Liste der Verbindungen halten kann.
Formale Beschreibung des Algorithmus
(1) Legen Sie die Anzahl der Oberseite, von der die Suche beginnt, in der leeren Zeile.
(2) Um den Peak U von Anfang an zu entfernen und wie in einem separaten Satz verwendet zu markieren.
(3) Am Ende der Warteschlange fügen Sie alle Spitzen, die wir durch die Rippen von der Oberseite von U erreichen können und die noch nicht markiert sind.
(4) Ist die Zeile leer, wurden alle Links der Kontaktbox überprüft, andernfalls zurück zu Absatz 2.
Komplexität der Arbeit
Da im schlimmsten Fall der Algorithmus alle Zähl- ' s Knoten besucht, während die Zählung in Form einer Liste von Verbindungen, die temporäre Komplexität des Algorithmus ist O(Vа + аEа), wo V ist viele Spitzen der Reihe und E ist viele Rippen.
Mit anderen Worten, der Algorithmus funktioniert schlimmstenfalls für die Anzahl der Rippen + die Oberseite.

Problem

Einige Dörfer sind durch Straßen verbunden, die sich als eine unvorhergesehene Anzahl vorstellen können. Die Spitze der Reihe ist Dörfer und die Rippen sind Straßen zwischen Dörfern (die Grafik kann Zyklen enthalten). Es ist bekannt, dass im DorfS Gegründet von einem Archel Schachteln♪ Jeden Morgen, um ihren kleinen Galante zu verkaufen, gehen die Boxer zu Dörfern, die noch nicht besucht wurden und eine Straße von der Strömung haben. Die Rüstung des Koroners ist immer in Gruppen unterteilt, so dass sie durch alle Dörfer, die Straßen von der aktuellen einen Tag haben.
Wie viele Tage werden die Boxer alle Dörfer besuchen? Schreib die Funktion. - Ja.die zur Aufgabe zurückkehren wird.


Eingangsdaten
Die erste Zeile stellt 3 ganze Zahlen vor n♪ m♪ s (seufzt)- Ja.♪ - Ja.♪ - Ja.( Die Anzahl der Dörfer, die Anzahl der Straßen zwischen ihnen und die Anzahl des Dorfes, in dem der Koroner gegründet wird. Nächste m 2 Zeilen u♪ v(seufzt)- Ja.Anzahl von zwei Dörfern, zwischen denen die Straße ist. Dorf Injektion 1♪

Ausgangsdaten
Nehmen Sie eine Nummer aus, für wie viele Tage die Boxen werden alle Dörfer besuchen.
Beispiele
NeinEingangsdatenAusgangsdaten
16 7 1
Artikel 2
Artikel 1
Artikel 3
ANHANG
Artikel 4
3 6
4 6		ANHANG

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