Module: Derinlemesine arayın. DFS


Problem

2/12

DFS: Başlat (Python)

Theory Click to read/hide

DFS DFS
Önce derinlik araması (DFS), grafiklerdeki ana algoritmalardan biridir. Algoritma O(N + M) şeklinde çalışır.
 
Algoritma
Başlangıç ​​olarak tepeden başlıyoruz, bu tepenin çocuklarını ele alıyoruz ve onları hiç girmemişsek onlardan DFS başlatıyoruz.


Problem

Yönlendirilmemiş bir grafiğin derinliğini S başlangıç ​​köşe noktasından kateden ve tepe noktasından başlayarak tüm köşeleri geçiş sırasına göre çıkaran bir prosedür def dfs(v) yazın < code>S bir satırda boşlukla ayrılmış.

İlk satır üç sayı içerir N  - grafikteki köşe sayısı, M - kenarların sayısı, S - başlangıç tepe noktası Aşağıdaki M satırlarında 2 değişken Ui ve Vi sağlanır , grafik kenarlarının açıklaması. Girişteki tüm sayılar 1000'i geçmez.

Tüm köşeleri, geçiş sırasına göre  DFS ile çıktılayın.

Yukarıdaki programda V[i][j], i ve j köşeleri arasında bir kenar olduğu anlamına gelir ve Ziyaret Edildi dizisi bu zirveyi ziyaret edip etmediğimizi işaretliyoruz. 
 
Girintiyi belirtmek için 4 boşluk kullanın.

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!