โปรแกรมตรวจสอบว่าสามารถเดินทางจากเมืองหนึ่งไปอีกเมืองหนึ่งได้หรือไม่ใน Python

สมมติว่ามี 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
  • mark i เป็น visited
  • สำหรับแต่ละ j ใน g[i] ถ้า j ไม่ได้ visited เรียก dfs(j, visited, g)
• กำหนดฟังก์ชัน travel() รับ g
  • visited := เซตใหม่
  • dfs(0, visited, g)
  • คืนค่า true ถ้าขนาด visited == n
• จากเมธอดหลัก
  • graph := map ว่าง, rev_graph := map ว่าง
  • สำหรับแต่ละ u, v ใน roads ใส่ v เข้า graph[u], ใส่ u เข้า rev_graph[v]
  • คืนค่า true ถ้า travel(graph) และ travel(rev_graph) ทั้งคู่เป็น true

ตัวอย่างโค้ด

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