Module: गहराई से खोजें। डीएफएस


Problem

2/12

डीएफएस: स्टार्ट (पायथन)

Theory Click to read/hide

डीएफएस <कोड>डीएफएस
डेप्थ फ़र्स्ट सर्च (DFS) ग्राफ़ पर मुख्य एल्गोरिदम में से एक है। एल्गोरिदम O(N + M) में चलता है।
 
एल्गोरिदम
शुरू करने के लिए हम ऊपर से शुरू करते हैं, इस चोटी के बच्चों पर विचार करते हैं, और अगर हमने कभी प्रवेश नहीं किया है, तो हम उनसे DFS शुरू करते हैं।


Problem

एक ऐसी प्रक्रिया लिखें def dfs(v) जो आरंभिक शीर्ष S से एक अप्रत्यक्ष ग्राफ की गहराई का पता लगाती है और सभी शीर्षों को ट्रैवर्सल क्रम में आउटपुट करती है, जो शीर्ष से शुरू होती है < कोड> एस एक पंक्ति पर एक स्थान से अलग किया गया।

पहली पंक्ति में तीन संख्याएँ हैं N  - ग्राफ़ में शीर्षों की संख्या, M - किनारों की संख्या, S - प्रारंभ शिखर। निम्नलिखित M पंक्तियों में, 2 चर Ui और Vi आपूर्ति की जाती हैं , ग्राफ किनारों का विवरण। इनपुट में सभी संख्याएं 1000 से अधिक नहीं हैं।

 DFS द्वारा ट्रैवर्सल के क्रम में सभी शीर्षों को आउटपुट करें।

ऊपर दिए गए प्रोग्राम में, V[i][j] का अर्थ है कि शीर्षों i और j के बीच एक किनारा है, और सरणी देखा गया हम चिह्नित करते हैं कि क्या हम इस चोटी पर गए थे। 
 
इंडेंटेशन इंगित करने के लिए 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!