प्रोग्राम यह जांचने के लिए कि क्या हम पायथन में सभी पाठ्यक्रम ले सकते हैं या नहीं

मान लीजिए कि हमारे पास एक 2डी मैट्रिक्स है जहां मैट्रिक्स [i] पाठ्यक्रम में दाखिला लेने के लिए आवश्यक पूर्वापेक्षा पाठ्यक्रमों की सूची का प्रतिनिधित्व करता है। अब, हमें यह देखना होगा कि सभी कोर्स करना संभव है या नहीं।

इसलिए, यदि इनपुट मैट्रिक्स =[[1],[2],[]] जैसा है, तो आउटपुट ट्रू होगा, क्योंकि हम कोर्स 2, फिर कोर्स 1, और फिर कोर्स 0 ले सकते हैं।

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

• फ़ंक्शन dfs () को परिभाषित करें। इसमें मुझे लगेगा

• अगर विज़ [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