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

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

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

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

• dfs() फंक्शन परिभाषित करें जो i लेता है
• यदि vis[i] सत्य है, तो असत्य वापस करें
• यदि chk[i] सत्य है, तो सत्य वापस करें
• vis[i] := सत्य
• matrix[i] में प्रत्येक j के लिए करें:
  • यदि dfs(j) असत्य है, तो असत्य वापस करें
• vis[i] := असत्य
• chk[i] := सत्य
• सत्य वापस करें
• मुख्य विधि से:
  • vis := matrix की पंक्ति संख्या के आकार की सूची, प्रारंभ में सभी असत्य
  • chk := matrix की पंक्ति संख्या के आकार की सूची, प्रारंभ में सभी असत्य
  • i को 0 से matrix की पंक्ति संख्या तक के लिए करें:
    • यदि 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