मान लीजिए, हमारे पास 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 होगा।
मैट्रिक्स ए को =
. के रूप में दिया गया है1 | 1 | 1 | 1 | 1 |
1 | 2 | 1 | 1 | 1 |
1 | 1 | 3 | 1 | 1 |
1 | 1 | 1 | 4 | 1 |
1 | 1 | 1 | 1 | 5 |
इस मैट्रिक्स का निर्धारक 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