मान लीजिए कि कुल n पाठ्यक्रम हैं, इन्हें 0 से n-1 तक लेबल किया गया है। कुछ पाठ्यक्रमों में पूर्वापेक्षाएँ हो सकती हैं, पाठ्यक्रमों की कुल संख्या और पूर्वापेक्षित जोड़ियों की सूची को देखते हुए, हमें उन पाठ्यक्रमों का क्रम खोजना होगा जिन्हें हमें सभी पाठ्यक्रमों को पूरा करने के लिए लेना चाहिए। कई सही आदेश हो सकते हैं, हमें बस उनमें से एक को खोजने की जरूरत है। यदि सभी पाठ्यक्रमों को पूरा करना असंभव है, तो एक खाली सरणी लौटाएं।
तो अगर इनपुट 2, [[1, 0]] जैसा है, तो परिणाम [0,1] होगा। कुल 2 कोर्स करने हैं। कोर्स नंबर 1 लेने के लिए हमें कोर्स 0 पूरा करना चाहिए था। इसलिए सही कोर्स ऑर्डर है [0,1]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मुख्य विधि में, यह numCourses, और पूर्वापेक्षाएँ लेगा:यह इस तरह कार्य करेगा -
-
इन_डिग्री नामक एक सरणी को परिभाषित करें, और सभी नोड्स की डिग्री में भरें, और adj :=ग्राफ़ की आसन्नता सूची
-
विज़िट नामक एक सरणी को परिभाषित करें, और इसे 0 से भरें, इसका आकार numCourses के समान है
-
एक खाली स्टैक को परिभाषित करें।
-
मेरे लिए 0 से numCourses की सीमा में
-
यदि विज़िट किया गया [i] झूठा है और नोड के dfs i में स्टैक पास करके झूठा है, तो
-
एक खाली सूची लौटाएं
-
-
-
स्टैक तत्वों को उल्टे क्रम में लौटाएं।
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution(object):
def findOrder(self, numCourses, prerequisites):
in_degree,adj=self.create_adj(numCourses,prerequisites)
visited = [0 for i in range(numCourses)]
stack = []
for i in range(numCourses):
if not visited[i] and not self.dfs(i,visited,stack,adj):
return []
return stack[::-1]
def create_adj(self,n,graph):
adj = {}
in_degree= [0 for i in range(n)]
for i in graph:
in_degree[i[0]]+=1
if i[1] in adj:
adj[i[1]].append(i[0])
else:
adj[i[1]] = [i[0]]
return in_degree,adj
def dfs(self, node, visited,stack,adj):
if visited[node] == -1:
return False
if visited[node] == 1:
return True
visited[node] = -1
if node in adj:
for i in adj[node]:
if not self.dfs(i,visited,stack,adj):
return False
visited[node]=1
stack.append(node)
return True
ob = Solution()
print(ob.findOrder(2, [[1,0]])) इनपुट
2 [[1,0]]
आउटपुट
[0,1]