পাইথনে সকল কোর্স কভার করতে ন্যূনতম সেমিস্টার গণনার প্রোগ্রাম

মান লিজিয়ে n সংখ্যক ভিন্ন কোর্স আছে যা ১ থেকে n পর্যন্ত লেবেলড। আরেকটি অ্যারে আছে relations যেখানে relations[i] একটি জোড়া (prevCourse_i, nextCourse_i) ধারণ করে, যা prevCourse_i এবং nextCourse_i কোর্সের মধ্যে প্রি-রেকুইজিট সম্পর্ক বোঝায়: অর্থাৎ prevCourse_i কোর্সটি nextCourse_i কোর্সের আগে নিতে হবে। এবং শেষ প্যারামিটার হল k। এক সেমিস্টারে আমরা সর্বোচ্চ k সংখ্যক কোর্স নিতে পারি যতক্ষণ না আমরা আগের সেমিস্টারে সেই কোর্সগুলোর সকল প্রি-রেকুইজিট নেওয়া থাকে। সকল কোর্স নিতে ন্যূনতম কত সেমিস্টার লাগবে সেটি বের করতে হবে।

যেমন, ইনপুট হলে (চিত্র দেখুন), তবে আউটপুট হবে 3 কারণ প্রথম সেমিস্টারে কোর্স ১ ও ২ নেওয়া যায়, এখন কোর্স ৩, ৪, ৫-এর জন্য যোগ্য হয়ে উঠল। দ্বিতীয় সেমিস্টারে ৫ এবং ৩ বা ৪ যেকোনো একটি নিলে, তৃতীয় সেমিস্টারে বাকি কোর্সগুলো শেষ করা যায়। মোট ৩ সেমিস্টার লাগবে।

সমাধানের ধাপসমূহ

taken := নতুন সেট
g1 := n` সাইজের খালি লিস্টের লিস্ট
g2 := n` সাইজের লিস্ট ০ দিয়ে ফিল করা
w := n` সাইজের লিস্ট ০ দিয়ে ফিল করা
semester := 0
relations-এ প্রতিটি x এর জন্য:
- g1[x[1]-1].append(x[0]-1)
- g2[x[0]-1].append(x[1]-1)
weight := g1-এর সব আইটেমের দৈর্ঘ্য থেকে তৈরি লিস্ট
i = 0 থেকে n-1 পর্যন্ত:
- g1[i]-এ প্রতিটি x এর জন্য: w[x] = max(w[x], weight[i])
len(taken) < n থাকা পর্যন্ত:
- courses := নতুন লিস্ট
- i = 0 থেকে n-1 পর্যন্ত:
  - যদি g1[i] খালি হয় এবং i not in taken, তবে courses.append([i, w[i]])
- যদি len(courses) > k হয়, তবে:
  - courses কে দ্বিতীয় প্যারামিটার অনুযায়ী রিভার্স সর্ট করুন
  - courses := courses[:k]
- semester := semester + 1
- courses-এ প্রতিটি x এর জন্য:
  - g2[x[0]]-এ প্রতিটি y এর জন্য: g1[y].remove(x[0])
  - g2[x[0]] := []
  - taken.add(x[0])
semester রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(n, relations, k):
    taken = set()
    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]
    w = [0] * n
    semester = 0
    for x in relations:
        g1[x[1]-1].append(x[0]-1)
        g2[x[0]-1].append(x[1]-1)
    weight = list(map(len, g1))
    for i in range(n):
        for x in g1[i]:
            w[x] = max(w[x], weight[i])
    while len(taken) < n:
        courses = []
        for i in range(n):
            if (not g1[i]) and (i not in taken):
                courses.append([i, w[i]])
        if len(courses) > k:
            courses = sorted(courses, key=lambda x: x[1], reverse=True)
            courses = courses[:k]
        semester += 1
        for x in courses:
            for y in g2[x[0]]:
                g1[y].remove(x[0])
            g2[x[0]] = []
            taken.add(x[0])
    return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

ইনপুট

6, [(1,3),(2,5),(2,4),(5,6)], 2