আমরা পাইথনে সমস্ত কোর্স করতে পারি কি না তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে যেখানে ম্যাট্রিক্স[i] কোর্স i নথিভুক্ত করার জন্য প্রয়োজনীয় পূর্বশর্ত কোর্সের তালিকা উপস্থাপন করে। এখন, আমাদের পরীক্ষা করতে হবে সব কোর্স করা সম্ভব কি না।

সুতরাং, যদি ইনপুট ম্যাট্রিক্স =[[1],[2],[]] এর মত হয়, তাহলে আউটপুট হবে True, যেহেতু আমরা কোর্স 2, তারপর কোর্স 1 এবং তারপর কোর্স 0 নিতে পারি।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য i

  লাগবে

• যদি vis[i] সত্য হয়, তাহলে

  • ফেরত মিথ্যা

• যদি chk[i] সত্য হয়, তাহলে

  • রিটার্ন ট্রু

• vis[i]:=সত্য

• ম্যাট্রিক্স[i]-এ প্রতিটি j-এর জন্য করুন

  • যদি dfs(j) মিথ্যা হয়, তাহলে

    • রিটার্ন ফলস

• vis[i]:=মিথ্যা

• chk[i]:=সত্য

• রিটার্ন ট্রু

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• vis:=ম্যাট্রিক্সের সারি গণনার সমান আকারের একটি তালিকা এবং প্রাথমিকভাবে সবই মিথ্যা

• chk:=ম্যাট্রিক্সের সারি গণনার সমান আকারের একটি তালিকা এবং প্রাথমিকভাবে সবই মিথ্যা

• ম্যাট্রিক্সের 0 থেকে সারি গণনার রেঞ্জের জন্য, করুন

  • যদি dfs(i) মিথ্যা হয়, তাহলে

    • রিটার্ন ফলস

• রিটার্ন ট্রু

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

উদাহরণ

class Solution:
   def solve(self, matrix):
      vis=[False for _ in matrix]
      chk=[False for _ in matrix]
      def dfs(i):
         if vis[i]: return False
         if chk[i]: return True
         vis[i]=True
         for j in matrix[i]:
            if not dfs(j):
               return False
         vis[i]=False
         chk[i]=True
         return True
   for i in range(len(matrix)):
      if not dfs(i):
         return False
   return True
ob = Solution()
matrix = [ [1], [2], [] ]
print(ob.solve(matrix))

ইনপুট

matrix = [
   [1],
   [2],
   []
]

আউটপুট

True