找出给定特殊矩阵的行列式的 Python 程序

假设,我们有一棵树有 n 个顶点,其中每个顶点的标签从 1 到 n。树的根标签为 1,每个顶点的权重为 wi。现在形成了一个 nxn 矩阵 A 其中A(x,y)= Wf(x, y)wheref(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 给出为 =

11111
12111
11311
11141
11115

这个矩阵的行列式是 24。

示例

让我们看看以下实现以获得更好的理解 -

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