মনে করুন মোট nটি কোর্স আছে, সেগুলো ০ থেকে n-1 পর্যন্ত লেবেল করা। কিছু কোর্সের প্রি-রেকুইজিট থাকতে পারে। মোট কোর্স সংখ্যা এবং প্রি-রেকুইজিট পেয়ার লিস্ট দেওয়া থাকলে, সকল কোর্স শেষ করার জন্য কী ক্রমে কোর্স নেওয়া উচিত সেটি বের করতে হবে। একাধিক সঠিক ক্রম থাকতে পারে, আমাদের শুধু একটি খুঁজে বের করতে হবে। যদি সব কোর্স শেষ করা অসম্ভব হয়, তবে খালি অ্যারে রিটার্ন করুন।
ইনপুট যদি 2, [[1, 0]] হয়, তবে রেজাল্ট হবে [0,1]। মোট ২টি কোর্স। কোর্স ১ নেওয়ার আগে কোর্স ০ শেষ করতে হবে। তাই সঠিক ক্রম [0,1]।
এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (টপোলজিক্যাল সোর্ট + সাইকেল ডিটেকশন):
মেইন মেথড
numCoursesএবংprerequisitesনেবে:in_degreeঅ্যারে বানান সব নোডের ইন-ডিগ্রি দিয়ে, এবংadjঅ্যাডজেসেন্সি লিস্ট।visitedঅ্যারে ০ দিয়ে পূরণ, সাইজnumCourses।একটি খালি
stack।for i in range 0 to numCourses:যদি
visited[i]false এবংdfs(i)false রিটার্ন করে (স্ট্যাক পাস করে), তবে খালি লিস্ট রিটার্ন করুন।
stack-এর এলিমেন্টগুলো রিভার্স অর্ডারে রিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।
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]
