在Python中计算包括给定边的独特路径数的程序

假设我们有一个边的列表，形式为(u, v)，它们表示一棵树。对于每条边，我们必须找到包括该边的总唯一路径数，按照输入中给定的顺序。

所以，如果输入是这样的边= [[0,1]，[0,2]，[1,3]，[1,4]]

那么输出将是[6,4,4,4]。

为了解决这个问题，我们将执行以下步骤 –

• adj：从给定的边缘建立邻接列表

• count：一个空映射

• 定义一个函数dfs()。这将采取x，parent

• count [x]：= 1

• 对于每个adj [x]中的nb，请执行以下操作 –

  • 如果nb与parent相同，则继续

  • count [x] = count [x] + dfs（nb，x）

• 返回计数[x]

• 从主方法执行以下操作 –

• dfs（0，-1）

• ans：一个新列表

• 对于边界中的每个边缘（a，b），请执行以下操作 –

  • x：=计数[a]和计数[b]的最小值

  • 在ans末尾插入（x*（count[0] – x)）

• 返回ans

示例

让我们看一下以下实现，以更好地理解 –

from collections import defaultdict
class Solution:
   def solve(self, edges):
      adj = defaultdict(list)
      for a, b in edges:
         adj[a].append(b)
         adj[b].append(a)
      count = defaultdict(int)
      def dfs(x, parent):
         count[x] = 1
         for nb in adj[x]:
            if nb == parent:
               continue
            count[x] += dfs(nb, x)
         return count[x]
      dfs(0, -1)
      ans = []
      for a, b in edges:
         x = min(count[a], count[b])
         ans.append(x * (count[0] - x))
      return ans
ob = Solution()
edges = [
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
]
print(ob.solve(edges))

输入

[
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
]

输出

[6, 4, 4, 4]