পাইথনে নির্দেশিত গ্রাফটি বিপরীত করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি নির্দেশিত গ্রাফ আছে, আমাদের এটির বিপরীতটি খুঁজে বের করতে হবে তাই যদি একটি প্রান্ত u থেকে v তে যায় তবে এটি এখন v থেকে u তে যায়। এখানে ইনপুট একটি সংলগ্ন তালিকা হবে, এবং যদি n নোড থাকে তবে নোডগুলি হবে (0, 1, ..., n-1)।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=n বিভিন্ন তালিকার একটি তালিকা, যেখানে n হল শীর্ষবিন্দুর সংখ্যা
• প্রতিটি সূচক i, এবং গ্রাফে সংলগ্ন তালিকার জন্য, করুন
  • l এর প্রতিটি x এর জন্য, করুন
    • ans[x] এর শেষে i ঢোকান
• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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