โปรแกรมตรวจสอบเราสามารถเยี่ยมชมเมืองใด ๆ จากเมืองใด ๆ หรือไม่ใน Python

สมมติว่าเรามีเมือง n เมืองที่แสดงเป็นตัวเลขในช่วง [0, n) และเรายังมีรายการถนนเดินรถทางเดียวที่เชื่อมเมืองหนึ่งไปยังอีกเมืองหนึ่ง เราต้องเช็คก่อนว่าจะไปถึงเมืองไหนจากเมืองไหนได้บ้าง

ดังนั้น ถ้าอินพุตเป็น n =3 ถนน =[[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]] จากนั้นผลลัพธ์จะเป็น True เนื่องจากคุณสามารถไปที่ 0 ถึง 1 และ 1 ถึง 0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• กำหนดฟังก์ชัน dfs() นี้จะพาฉันไป, เยี่ยมชม, g

• ทำเครื่องหมายว่าเยี่ยมชมแล้ว

• สำหรับแต่ละ j ใน g[i] ทำ

  • ถ้าเจไม่ได้มาเยี่ยมแล้ว

    • dfs(j, เยี่ยมชม, g)

• กำหนดฟังก์ชัน travel() นี่จะใช้เวลา g

• เข้าชมแล้ว :=ชุดใหม่

• dfs(0, เยี่ยมชม, g)

• คืนค่าจริงเมื่อขนาดของการเยี่ยมชมเท่ากับ n

• จากวิธีหลัก ให้ทำดังนี้−

• กราฟ :=แผนที่ว่าง

• rev_graph :=แผนที่ว่างเปล่า

• สำหรับแต่ละต้นทาง u และปลายทาง v ในถนน ทำ

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้าย rev_graph[v]

• คืนค่าจริงเมื่อ 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