पायथन में कोर्स शेड्यूल

मान लीजिए कुल numCourses कोर्स हैं जिन्हें हमें लेना है, 0 से numCourses-1 तक लेबल किए गए। कुछ कोर्स के प्रीरिक्विज़िट्स हो सकते हैं, उदाहरण के लिए कोर्स 0 लेने के लिए हमें पहले कोर्स 1 लेना होगा, जिसे एक जोड़ी का उपयोग करके व्यक्त किया जाता है: [0,1]। मान लीजिए कुल कोर्स की संख्या प्रदान की गई है और प्रीरिक्विज़िट जोड़े की लिस्ट है, हमें जांचना है कि क्या आपके लिए सभी कोर्स खत्म करना संभव है?

इसलिए यदि इनपुट numCourses = 2 और prerequisites = [[1, 0]] जैसा है, तो परिणाम true होगा, क्योंकि लेने के लिए कुल 2 कोर्स हैं। कोर्स 1 लेने के लिए हमें कोर्स 0 खत्म करना चाहिए। तो यह संभव है।

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

• मुख्य मेथड में, यह numCourses, और prerequisites लेगा: यह इस तरह कार्य करेगा -

• यदि prerequisites में कोई एंट्री नहीं है, तो true लौटाएं

• visited नामक एक ऐरे बनाएं, इसे 0 से भरें, और इसकी रेंज numCourses के समान है

• adj_list := prerequisites का उपयोग करके ग्राफ बनाएं

• i को 0 से numCourses तक रेंज में

  • यदि visited[i] false है, तो

    • यदि विजिटेड नोड्स में ग्राफ में कोई साइकिल नहीं है, तो false लौटाएं

• true लौटाएं

उदाहरण

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        if len(prerequisites) == 0:
            return True
        visited = [0 for i in range(numCourses)]
        adj_list = self.make_graph(prerequisites)
        for i in range(numCourses):
            if not visited[i]:
                if not self.cycle(adj_list,visited,i):
                    return False
        return True
    def cycle(self,adj_list,visited,current_node = 0):
        if visited[current_node] ==-1:
            return False
        if visited[current_node] == 1:
            return True
        visited[current_node] = -1
        if(current_node in adj_list):
            for i in adj_list[current_node]:
                if not self.cycle(adj_list,visited,i):
                    return False
        visited[current_node] = 1
        return True
    def make_graph(self,array):
        adj_list = {}
        for i in array:
            if i[1] in adj_list:
                adj_list[i[1]].append(i[0])
            else:
                adj_list[i[1]] = [i[0]]
        return adj_list

ob = Solution()
print(ob.canFinish(2, [[1,0]]))

इनपुट

2 [[1,0]]

आउटपुट

true