Problem

2/12

DFS: ابدأ (بايثون)

Theory Click to read/hide

DFS & nbsp؛ DFS
يعد بحث العمق الأول ( DFS ) أحد الخوارزميات الرئيسية في الرسوم البيانية. تعمل الخوارزمية في O (N + M) .
نبسب ؛
الخوارزمية بادئ ذي بدء ، نبدأ من الأعلى ، ونفكر في أطفال هذا الجزء العلوي ، وإذا لم نقم بإدخالهم مطلقًا ، فسنبدأ منهم DFS .


Problem

اكتب إجراء def dfs (v) يمر بعمق رسم بياني غير موجه من قمة البداية S ويخرج جميع القمم بترتيب اجتياز ، بدءًا من قمة الرأس < code> S مفصولة بمسافة في سطر واحد.

يحتوي السطر الأول على ثلاثة أرقام N & nbsp؛ - عدد الرؤوس في الرسم البياني ، M - عدد الحواف ، S - البداية قمة الرأس. في سطور M التالية ، متغيرين U i و V i يتم توفيرها ، وصف حواف الرسم البياني. جميع الأرقام في الإدخال لا تتجاوز 1000.

إخراج جميع القمم بترتيب الاجتياز بواسطة & nbsp؛ DFS .

في البرنامج أعلاه ، تعني & nbsp؛ V [i] [j] أن هناك حافة بين القمم i و j ، وفي المصفوفة <كود> تمت زيارته & nbsp ؛ نحدد ما إذا كنا قد قمنا بزيارة هذه الذروة. & nbsp؛
نبسب ؛
استخدم 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
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!