Module: Suche in die Tiefe. DFS


Problem

2/12

DFS: Anfang (Python)

Theory Click to read/hide

Suche tief.DFS
Erkennung tief.DFS) ist einer der Hauptalgorithmen auf den Zählungen. Algorithm arbeitet für O(N + M)♪
Algorithmen
Für Anfänger beginnen wir von oben, schauen uns die Kinder dieses Tops an, und wenn wir nie reingekommen sind, fangen wir mit ihnen an. DFS♪


Problem

Schreiben Sie eine def dfs(v)-Prozedur, die einen nicht ausgerichteten Graphen vom Anfangsscheitelpunkt S in die Tiefe umgeht und alle Eckpunkte in der Durchforstungsreihenfolge ab dem Eckpunkt S durch ein Leerzeichen in einer Zeile ausgibt.

In der ersten Zeile sind drei Zahlen angegeben: N - die Anzahl der Scheitelpunkte im Diagramm, M - die Anzahl der Kanten, S - der Startscheitelpunkt. Die folgenden M Zeilen enthalten 2 Variablen Ui und Vi, die die Kanten des Diagramms beschreiben. Alle Zahlen in den Eingaben überschreiten 1000 nicht.

Geben Sie alle Stützpunkte in der durchforsteten Reihenfolge durch denDFS -Algorithmus aus.

Im obigen Programm bedeutetV[i][j], dass es eine Kante zwischen den Eckpunkten i und j gibt, und im Array Visited markieren wir, ob wir diesen Eckpunkt erreicht haben. 
 
Verwenden Sie 4 Leerzeichen, um die Einrückung anzugeben.

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 dfs(start):      
n, m, s = map(int, input().split())
Visited = [False]*(n+1)
V = [set() for i in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    V[u].add(v)
    V[v].add(u)

dfs(s)

     

Program check result

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