Python में दिए गए विशेष मैट्रिक्स का डिटरमिनेंट खोजने का प्रोग्राम

मान लीजिए, हमारे पास n वर्टेक्स वाला एक ट्री है, जहां प्रत्येक वर्टेक्स 1 से n तक लेबल किया गया है। ट्री का रूट लेबल 1 है, और प्रत्येक वर्टेक्स का वजन wi है। अब एक n×n मैट्रिक्स A बनाया जाता है जहां A(x,y) = Wf(x, y) जहां f(x, y) वर्टेक्स x और y का लीस्ट कॉमन प्रीडिसेसर है। हमें मैट्रिक्स A का डिटरमिनेंट ढूंढना है। मैट्रिक्स के एज, वजन, और वर्टेक्स की कुल संख्या इनपुट के रूप में दी गई है।

इसलिए, यदि इनपुट है: input_array = [[1, 2], [1, 3], [1, 4], [1, 5]], weights = [1, 2, 3, 4, 5], vertices = 5, तो आउटपुट 24 होगा।

मैट्रिक्स A निम्न है:

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 := एक खाली सूची
i को 0 से vertices तक के लिए: weights[i] और एक नई सूची को w में जोड़ें
input_array में प्रत्येक i, item के लिए:
- p := item[0], q := item[1]
- w[p-1][1] के अंत में q-1 डालें
- w[q-1][1] के अंत में p-1 डालें
det := 1
stack := (0, 0) टपल वाला एक स्टैक
जब स्टैक खाली नहीं है:
- i, weights := स्टैक से टॉप तत्व हटाएं
- det := (det * (w[i][0] - weights)) mod (10^9 + 7)
- w[i][1] में प्रत्येक t के लिए:
  - स्टैक में (t, w[i][0]) टपल जोड़ें
  - w[i][1] में प्रत्येक t के लिए: 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