ধরুন মোট n কোর্স আছে, সেগুলিকে 0 থেকে n-1 পর্যন্ত লেবেল করা হয়েছে৷ কিছু কোর্সের পূর্বশর্ত থাকতে পারে, কোর্সের মোট সংখ্যা এবং পূর্বশর্ত জোড়ার একটি তালিকা দেওয়া হলে, আমাদের কোর্সের ক্রম খুঁজে বের করতে হবে যা আমাদের সমস্ত কোর্স শেষ করতে হবে। একাধিক সঠিক আদেশ থাকতে পারে, আমাদের কেবল তাদের মধ্যে একটি খুঁজে বের করতে হবে। যদি সমস্ত কোর্স শেষ করা অসম্ভব হয়, তাহলে একটি খালি অ্যারে ফেরত দিন।
সুতরাং ইনপুট যদি 2, [[1, 0]] এর মত হয়, তাহলে ফলাফল হবে [0,1]। এখানে মোট 2টি কোর্স নেওয়ার আছে। কোর্স নম্বর 1 নিতে আমাদের অবশ্যই 0 কোর্স শেষ করা উচিত। তাই সঠিক কোর্সের ক্রম হল [0,1]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
প্রধান পদ্ধতিতে, এটি numCourses এবং পূর্বশর্তগুলি নেবে:এটি এরকম কাজ করবে −
-
in_degree নামক একটি অ্যারে সংজ্ঞায়িত করুন এবং সমস্ত নোডের সমস্ত ডিগ্রী দিয়ে পূরণ করুন এবং adj :=গ্রাফের সংলগ্ন তালিকা
-
পরিদর্শন নামে একটি অ্যারে সংজ্ঞায়িত করুন এবং এটি 0 দিয়ে পূরণ করুন, এটির আকার numCourses
-
একটি খালি স্ট্যাক সংজ্ঞায়িত করুন।
-
আমি 0 থেকে numCourses এর মধ্যে
-
যদি পরিদর্শন করা [i] মিথ্যা হয় এবং নোড i এর dfs স্ট্যাক পাস করে মিথ্যা হয়, তাহলে
-
একটি খালি তালিকা ফেরত দিন
-
-
-
স্ট্যাক উপাদানগুলি বিপরীত ক্রমে ফেরত দিন।
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
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]
