यह जांचने के लिए कार्यक्रम कि हम किसी भी शहर से किसी भी शहर की यात्रा कर सकते हैं या नहीं, पायथन में

मान लीजिए कि हमारे पास n शहर हैं जिन्हें [0, n) की श्रेणी में एक संख्या के रूप में दर्शाया गया है और हमारे पास एक तरफ़ा सड़कों की एक सूची भी है जो एक शहर को दूसरे शहर से जोड़ती है। हमें यह जांचना होगा कि क्या हम किसी शहर से किसी शहर तक पहुंच सकते हैं।

इसलिए, यदि इनपुट n =3 जैसा है, तो सड़कें =[[0, 1], [0, 2], [1,0], [1,2], [2,0], [2,1]] , तो आउटपुट ट्रू होगा, क्योंकि आप 0 से 1 और 1 से 0 तक जा सकते हैं

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• फ़ंक्शन को परिभाषित करें dfs() । इसमें मुझे, विज़िट किया गया, g

  . लगेगा

• मुझे विज़िट किया गया के रूप में चिह्नित करें

• g[i] में प्रत्येक j के लिए, करें

  • अगर j का दौरा नहीं किया जाता है, तो

    • dfs(j, विज़िट किया गया, g)

• एक फ़ंक्शन यात्रा () को परिभाषित करें। इसमें जी लगेगा

• विज़िट किया गया :=एक नया सेट

• dfs(0, विज़िट किया गया, g)

• जब विज़िट का आकार n के समान हो तो सही लौटें

• मुख्य विधि से, निम्न कार्य करें-

• ग्राफ़ :=एक खाली नक्शा

• Rev_graph :=एक खाली नक्शा

• सड़कों में प्रत्येक स्रोत u, और गंतव्य v के लिए, करें

  • ग्राफ़ के अंत में v डालें[u]

  • आपको Rev_graph[v]

    . के अंत में डालें

• जब यात्रा (ग्राफ) और यात्रा (rev_graph) दोनों सत्य हों तो सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, n, roads):
      from collections import defaultdict
         graph = defaultdict(list)
         rev_graph = defaultdict(list)
   for u, v in roads:
      graph[u].append(v)
      rev_graph[v].append(u)
      def dfs(i, visited, g):
      visited.add(i)
   for j in g[i]:
      if j not in visited:
         dfs(j, visited,g)
         def travel(g):
         visited = set()
         dfs(0, visited, g)
      return len(visited)==n
   return travel(graph) and travel(rev_graph)
ob = Solution()
n = 3
roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
print(ob.solve(n, roads))

इनपुट

3, [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]

आउटपुट

True