資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算包含給定邊的唯一路徑數量
假設我們有一組邊，格式為 (u, v)，它們表示一棵樹。對於每條邊，我們必須找到包含該邊的所有唯一路徑的數量，順序與輸入中給出的順序相同。
例如，如果輸入是 edges = [[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)
返回 count[x]
在主方法中執行以下操作：
dfs(0, -1)
ans := 一個新的列表
對於 edges 中的每條邊 (a, b)：
x := count[a] 和 count[b] 中的最小值
將 (x *(count[0] - x)) 新增到 ans 的末尾
返回 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]
更新於：2020年12月22日
288 次瀏覽
廣告