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