পাইথনে সব কোর্স নেওয়া সম্ভব কিনা যাচাই করার প্রোগ্রাম

মনে করুন একটি ২ডি ম্যাট্রিক্স আছে যেখানে matrix[i] হল কোর্স i নেওয়ার জন্য প্রয়োজনীয় প্রিকোয়ারিজিট কোর্সের তালিকা। আমাদের যাচাই করতে হবে সব কোর্স নেওয়া সম্ভব কিনা।

উদাহরণস্বরূপ, matrix = [[1],[2],[]] হলে আউটপুট True, কারণ কোর্স ২, তারপর ১, তারপর ০ নেওয়া যায়।

সমাধানের ধাপসমূহ

• dfs() ফাংশন সংজ্ঞায়িত করুন যা i নেয়
• যদি vis[i] true হয়, তবে
  • false ফেরত দিন
• যদি chk[i] true হয়, তবে
  • True ফেরত দিন
• vis[i] := True
• প্রতিটি j matrix[i]-এ,
  • যদি dfs(j) false হয়, তবে
    • False ফেরত দিন
• vis[i] := False
• chk[i] := True
• True ফেরত দিন
• মূল মেথড থেকে:
  • vis := matrix-এর সারি সংখ্যা অনুযায়ী false দিয়ে তালিকা
  • chk := matrix-এর সারি সংখ্যা অনুযায়ী false দিয়ে তালিকা
  • i = 0 থেকে সারি সংখ্যা পর্যন্ত,
    • যদি dfs(i) false হয়, তবে
      • False ফেরত দিন
  • True ফেরত দিন

  উদাহরণ

  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