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

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

तो, अगर इनपुट पसंद है

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

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

• Ans :=n विभिन्न सूचियों की एक सूची, जहां n शीर्षों की संख्या है
• प्रत्येक अनुक्रमणिका i और ग्राफ़ में आसन्न सूची l के लिए, करते हैं
  • एल में प्रत्येक x के लिए, करें
    • उत्तर के अंत में i डालें[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]]