N সংখ্যক কোর্স আছে, ১ থেকে N পর্যন্ত লেবেলড। relations অ্যারেতে প্রি-রেকুইজাইট (prerequisite) রিলেশন দেওয়া আছে, যেখানে relations[i] = [X, Y] মানে কোর্স X আগে পড়তে হবে কোর্স Y-এর আগে।
এক সেমেস্টারে যেকোনো সংখ্যক কোর্স পড়া যায়, শর্ত হলো তার সব প্রি-রেকুইজাইট পুরো হয়ে থাকতে হবে। সব কোর্স পড়তে ন্যূনতম কত সেমেস্টর লাগবে বের করতে হবে। অসম্ভব হলে -1 রিটার্ন করবে।
যেমন, N = 3, relations = [[1,3], [2,3]] হলে আউটপুট ২, কারণ: ১ম সেমেস্টরে কোর্স ১ ও ২, ২য় সেমেস্টরে কোর্স ৩।
গ্রাফ এবং ইন-ডিগ্রি (in-degree) অ্যারে তৈরি করা।
ইন-ডিগ্রি ০ থাকা কোর্সগুলো কিউয়ে পুশ করা।
লেভেল বাই লেভেল (সেমেস্টর বাই সেমেস্টর) BFS চালানো।
প্রতিটি সেমেস্টরে কিউর সকল নোড প্রসেস করা।
যদি সব কোর্স পড়া শیشه না যায় তবে -1 রিটার্ন।
class Solution(object):
def minimumSemesters(self, n, relations):
courses = n
visited = [False] * (n + 1)
queue = []
graph = [[] for _ in range(n + 1)]
in_degree = [0] * (n + 1)
for u, v in relations:
graph[u].append(v)
in_degree[v] += 1
for i in range(1, n + 1):
if in_degree[i] == 0:
queue.append(i)
visited[i] = True
semester = 1
courses -= len(queue)
while queue and courses:
current_size = len(queue)
while current_size:
current_course = queue.pop(0)
current_size -= 1
for nei in graph[current_course]:
in_degree[nei] -= 1
if not visited[nei] and in_degree[nei] == 0:
courses -= 1
queue.append(nei)
visited[nei] = True
semester += 1
return semester if courses == 0 else -1
ob = Solution()
print(ob.minimumSemesters(3, [[1, 3], [2, 3]]))
3, [[1, 3], [2, 3]]
2
