पायथन में निर्देशित ग्राफ को उलटने का प्रोग्राम

मान लीजिए हमारे पास एक निर्देशित ग्राफ है, हमें इसका उल्टा ढूंढना है ताकि यदि एक किनारा u से v तक जाता है, तो अब यह v से u तक जाए। यहां इनपुट एक एडजेंसी सूची होगी, और यदि n नोड्स हैं, तो नोड्स (0, 1, ..., n-1) होंगे।

इसलिए, यदि इनपुट इस तरह है

तो आउटपुट होगा

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

• ans := n अलग-अलग सूचियों की एक सूची, जहां n शीर्षों की संख्या है
• प्रत्येक इंडेक्स i, और आसन्न सूची l के लिए graph में, करें
  • प्रत्येक x के लिए l में, करें
    • i को ans[x] के अंत में जोड़ें
• ans वापस करें

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

उदाहरण

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