পাইথনে সমান্তরাল কোর্স

ধরুন N কোর্স আছে, এবং এগুলোকে 1 থেকে N লেবেল করা হয়েছে। আমরা একটি রিলেশন অ্যারেও দিয়েছি, যেখানে সম্পর্ক[i] =[X, Y], কোর্স X এবং কোর্স Y এর মধ্যে একটি পূর্বশর্ত সম্পর্ক উপস্থাপন করছে। সুতরাং, এর মানে হল কোর্স Y এর আগে এক্স অধ্যয়ন করতে হবে।

একটি সেমিস্টারে আমরা যেকোন সংখ্যক কোর্স অধ্যয়ন করতে পারি যতক্ষণ না আমরা যে কোর্সটি অধ্যয়ন করছি তার সমস্ত পূর্বশর্ত অধ্যয়ন করেছি। সমস্ত কোর্স অধ্যয়নের জন্য আমাদের ন্যূনতম সেমিস্টারের সংখ্যা খুঁজে বের করতে হবে। এবং যদি সমস্ত কোর্স অধ্যয়ন করার কোন উপায় না থাকে, তাহলে -1 ফিরুন।

সুতরাং, যদি ইনপুট হয় N =3, সম্পর্ক =[[1,3],[2,3]], তাহলে আউটপুট হবে 2 কারণ প্রথম সেমিস্টারে, কোর্স 1 এবং 2 অধ্যয়ন করা হয়। দ্বিতীয় সেমিস্টারে, কোর্স 3 অধ্যয়ন করা হয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• কোর্স :=n

• পরিদর্শন করেছেন :=n+1 আকারের একটি অ্যারে, এবং এটি মিথ্যা দিয়ে পূরণ করুন

• সারি :=একটি নতুন তালিকা

• গ্রাফ :=n+1 সাবলিস্টের একটি তালিকা

• in_degree :=n+1 আকারের একটি অ্যারে, এবং এটি 0

  দিয়ে পূরণ করুন

• প্রতিটি সম্পর্কের জন্য, করুন

  • গ্রাফ[i[0]]

    এর শেষে i[1] সন্নিবেশ করুন

  • in_degree[i[1]] :=in_degree[i[1]] + 1

• সেমিস্টার :=1

• 1 থেকে n+1 রেঞ্জের জন্য, করুন

  • যদি in_degree[i] শূন্য হয়, তাহলে

    • সারির শেষে i ঢোকান

    • পরিদর্শন [i] :=সত্য

• সেমিস্টার :=1

• কোর্স :=কোর্স - সারির আকার

• যখন সারি খালি না থাকে এবং কোর্সগুলি অ-শূন্য থাকে, তাই করুন

  • current_size :=সারির আকার

  • কারেন্ট_সাইজ অ-শূন্য হলে, করুন

    • বর্তমান_কোর্স :=সারি[0]

    • সারি থেকে প্রথম উপাদান মুছুন

    • বর্তমান_আকার :=বর্তমান_আকার - 1

    • গ্রাফে প্রতিটি i জন্য [current_course], করুন

      • in_degree[i] :=in_degree[i] - 1

      • যদি i পরিদর্শন না করা হয় এবং in_degree[i] শূন্য হয়, তাহলে

        • কোর্স :=কোর্স - 1

        • সারির শেষে i ঢোকান

        • পরিদর্শন করেছেন[i]:=সত্য

  • সেমিস্টার :=সেমিস্টার + 1

• কোর্স 0 হলে সেমিস্টার ফেরত দিন অন্যথায় -1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution(object):
   def minimumSemesters(self, n, relations):
      courses = n
      visited = [False for i in range(n+1)]
      queue = []
      graph = [[] for i in range(n+1)]
      in_degree = [0 for i in range(n+1)]
      for i in relations:
         graph[i[0]].append(i[1])
         in_degree[i[1]]+=1
      semeseter = 1
      for i in range(1,n+1):
         if not in_degree[i]:
            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[0]
               queue.pop(0)
               current_size-=1
               for i in graph[current_course]:
                  in_degree[i]-=1
                  if not visited[i] and not in_degree[i]:
                     courses-=1
                     queue.append(i)
                  visited[i]=True
            semester+=1
         return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3,[[1,3],[2,3]]))

ইনপুট

3, [[1,3],[2,3]]

আউটপুট

-1