पायथन में जांचने का प्रोग्राम कि क्या किसी शहर से किसी अन्य शहर तक जाया जा सकता है

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

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

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

• dfs() फंक्शन परिभाषित करें जो i, visited, g लेता है:
  • i को विजिटेड मार्क करें
  • g[i] में प्रत्येक j के लिए करें:
    • यदि j विजिटेड नहीं है, तो dfs(j, visited, g)
• travel() फंक्शन परिभाषित करें जो g लेता है:
  • visited := एक नया सेट
  • dfs(0, visited, g)
  • सत्य वापस करें यदि visited का आकार n के बराबर है
• मुख्य विधि से:
  • graph := एक खाली मैप
  • rev_graph := एक खाली मैप
  • roads में प्रत्येक स्रोत u और गंतव्य v के लिए करें:
    • graph[u] के अंत में v डालें
    • rev_graph[v] के अंत में u डालें
  • सत्य वापस करें यदि travel(graph) और travel(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