পাইথনে ডায়रेक्टেড গ্রাফকে উল্টে ফেলার প্রোগ্রাম

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

যদি ইনপুট হয়:

তবে আউটপুট হবে:

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

• ans := n সংখ্যক আলাদা তালিকার একটি তালিকা, যেখানে n হল ভেরটেক্সের সংখ্যা।
• গ্রাফে থাকা প্রতিটি ইনডেক্স i এবং এডজেসেন্ট লিস্ট l-এর জন্য:
  • l-এ থাকা প্রতিটি x-এর জন্য:
    • 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]]