โปรแกรมกลับทิศทางกราฟแบบมีทิศทางใน Python

สมมติว่าเรามีกราฟแบบมีทิศทาง (directed graph) เราต้องหากราฟย้อนกลับ โดยถ้าเส้นเชื่อมไปจาก u ไป v จะกลายเป็นไปจาก v ไป u อินพุตเป็นรายการความติดกัน (adjacency list) ถ้ามี n โหนด โหนดจะเป็น (0, 1, ..., n-1)

ตัวอย่าง: กราฟต้นฉบับ [[1,2],[4],[4],[1,2],[3]] ผลลัพธ์คือ [[], [0, 3], [0, 3], [4], [1, 2]]

ขั้นตอนการแก้ปัญหา

1. สร้าง ans เป็นลิสต์ของ n ลิสต์ว่าง โดย n = จำนวนโหนด
2. สำหรับแต่ละ index i และรายการติดกัน l ใน graph:
   • สำหรับแต่ละ x ใน l:
     • เพิ่ม i เข้า ans[x]
3. คืนค่า ans

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

class Solution:
    def solve(self, graph):
        ans = [[] for _ in graph]
        for i, l in enumerate(graph):
            for x in l:
                ans[x].append(i)
        return ans

ob = Solution()
graph = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(graph))
# Output: [[], [0, 3], [0, 3], [4], [1, 2]]

อินพุต / เอาต์พุต

Input: [[1,2],[4],[4],[1,2],[3]]

Output: [[], [0, 3], [0, 3], [4], [1, 2]]