किसी दिए गए विशेष मैट्रिक्स के निर्धारक का पता लगाने के लिए पायथन प्रोग्राम

मान लीजिए, हमारे पास n शीर्षों वाला एक पेड़ है, जहां प्रत्येक शीर्ष को 1 से n तक लेबल किया गया है। पेड़ की जड़ में लेबल 1 होता है, और प्रत्येक शीर्ष का भार wi होता है। अब एक nxn मैट्रिक्स A बनता है जहाँ A(x,y) =Wf(x, y) जहाँ f(x, y) शीर्ष x और y का सबसे छोटा सामान्य पूर्ववर्ती है। हमें मैट्रिक्स ए के निर्धारक का पता लगाना है। मैट्रिक्स के किनारों, भार, और कुल शिखरों की संख्या हमें इनपुट के रूप में दी गई है।

तो, अगर इनपुट की तरह है input_array =[[1, 2], [1, 3], [1, 4], [1, 5]], weights =[1, 2, 3, 4, 5], कोने =5, तो आउटपुट 24 होगा।

मैट्रिक्स ए को =

इस मैट्रिक्स का निर्धारक 24 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• w :=एक खाली सूची
• मैं के लिए 0 से कोने तक की सीमा में, करते हैं
  • वज़न जोड़ें[i] और w में एक नई सूची
• प्रत्येक i के लिए, एन्यूमरेट में आइटम (input_array), do
  • p :=आइटम[0]
  • q:=आइटम[1]
  • w[p - 1, 1] के अंत में q - 1 डालें
  • w[q - 1, 1] के अंत में p-1 डालें।
• det :=1
• स्टैक :=एक स्टैक जिसमें टपल (0, 0) होता है
• जबकि स्टैक खाली नहीं है, करें
  • i, वज़न:=स्टैक से शीर्ष तत्व हटाएं
  • det :=(det * (w[i, 0] - weights)) mod (10^9 + 7)
  • t in w[i][1] के लिए, do
    • स्टैक में टपल युक्त (t,w[i,0]) जोड़ें
    • w[i][1] में प्रत्येक t के लिए,
      . करें
      • मुझे w[t,1] से हटाएं
• वापसी का विवरण

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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