在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]

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

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

示例

输入

输出

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

回顶部