একটি প্রদত্ত বিশেষ ম্যাট্রিক্সের নির্ধারক খুঁজে বের করতে পাইথন প্রোগ্রাম

ধরুন, আমাদের n শীর্ষবিন্দু সহ একটি গাছ আছে, যেখানে প্রতিটি শীর্ষকে 1 থেকে n পর্যন্ত লেবেল করা হয়েছে। গাছের মূলে 1 লেবেল রয়েছে এবং প্রতিটি শীর্ষের ওজন wi। এখন একটি nxn ম্যাট্রিক্স A গঠিত হয়েছে যেখানে A(x,y) =Wf(x, y) যেখানে f(x, y) শীর্ষবিন্দু x এবং y এর সর্বনিম্ন সাধারণ পূর্বসূরি। আমাদেরকে ম্যাট্রিক্স A-এর নির্ধারক খুঁজে বের করতে হবে। ম্যাট্রিক্সের প্রান্ত, ওজন এবং মোট শীর্ষবিন্দুর সংখ্যা আমাদের ইনপুট হিসাবে দেওয়া হয়েছে।

সুতরাং, যদি ইনপুটটি হয় input_array =[[1, 2], [1, 3], [1, 4], [1, 5]], ওজন =[1, 2, 3, 4, 5], শীর্ষবিন্দু =5, তাহলে আউটপুট হবে 24।

ম্যাট্রিক্স A =

এই ম্যাট্রিক্সের নির্ধারক হল 24।

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

• w :=একটি খালি তালিকা
• আমি 0 থেকে শীর্ষবিন্দু পর্যন্ত, কর
  • ওজন যোগ করুন[i] এবং w এ একটি নতুন তালিকা
• প্রতিটি i এর জন্য, গণনা (ইনপুট_অ্যারে) এ আইটেম করুন, করুন
  • p :=আইটেম[0]
  • q :=আইটেম[1]
  • w[p - 1, 1] এর শেষে q - 1 ঢোকান]
  • w[q - 1, 1] এর শেষে p - 1 ঢোকান]
• det :=1
• স্ট্যাক :=একটি স্ট্যাক যাতে একটি টিপল থাকে (0, 0)
• স্ট্যাক খালি না থাকার সময়, করুন
  • i, weights :=স্ট্যাক থেকে শীর্ষ উপাদান মুছুন
  • det :=(det * (w[i, 0] - ওজন)) মোড (10^9 + 7)
  • t এর জন্য w[i][1], করুন
    • স্ট্যাকে (t,w[i,0]) টিপল যুক্ত করুন
    • w[i][1]-এ প্রতিটি টি-এর জন্য, করুন
      • w[t,1] থেকে i মুছুন
• রিটার্ন det

উদাহরণ

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

def solve(input_array, weights, vertices):
   w = [[weights[i],[]] for i in range(vertices)]
   for i, item in enumerate(input_array):
      p,q = item[0], item[1]
      w[p - 1][1].append(q - 1)
      w[q - 1][1].append(p - 1)
   det = 1
   stack = [(0,0)]
   while stack:
      i, weights = stack.pop()
      det = (det * (w[i][0] - weights)) % (10**9 + 7)
      stack += [(t,w[i][0]) for t in w[i][1]]
      for t in w[i][1]:
         w[t][1].remove(i)
   return det
print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))

ইনপুট

[[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5

আউটপুট

24