โปรแกรมย้อนกลับกราฟกำกับใน Python

สมมุติว่าเรามีกราฟกำกับ, เราต้องหาการกลับกันของมัน ดังนั้นหากขอบเปลี่ยนจาก u ไป v, ตอนนี้ มันไปจาก v ไปที่ u อินพุตนี้จะเป็นรายการที่อยู่ติดกัน และหากมี n โหนด โหนดจะเป็น (0, 1, ..., n-1)

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

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

• ans :=รายการของ n รายการที่แตกต่างกัน โดยที่ n คือจำนวนจุดยอด
• สำหรับแต่ละดัชนี i และรายการที่อยู่ติดกัน l ในกราฟ ทำ
  • สำหรับแต่ละ x ใน l ทำ
    • ใส่ i ต่อท้าย ans[x]
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

[[1,2],[4],[4],[1,2],[3]]

ผลลัพธ์

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