資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在Python中查詢樹中距離恰好為k的不同頂點對的數量
假設我們有一個整數k，還有一個具有n個節點的樹，我們必須計算距離恰好為k的不同頂點對的數量。
因此，如果輸入如下：k = 2
則輸出為4
為了解決這個問題，我們將遵循以下步驟：
N := 5005
graph := 大小為N的鄰接表
vertex_count := 大小為505 x 5005的二維矩陣
res := 0
定義一個函式insert_edge()。它將接收x, y
將y插入graph[x]的末尾
將x插入graph[y]的末尾
定義一個函式dfs()。它將接收v, parent
vertex_count[v, 0] := 1
對於graph[v]中的每個i，執行：
如果i與parent不同，則
dfs(i, v)
對於範圍1到k + 1中的每個j，執行：
res := res + vertex_count[i, j - 1] * vertex_count[v, k - j]
對於範圍1到k + 1中的每個j，執行：
vertex_count[v, j] := vertex_count[v, j] + vertex_count[i, j - 1]
示例
讓我們來看下面的實現以更好地理解：
N = 5005 graph = [[] for i in range(N)] vertex_count = [[0 for i in range(505)] for i in range(N)] res = 0 def insert_edge(x, y): graph[x].append(y) graph[y].append(x) def dfs(v, parent): global res vertex_count[v][0] = 1 for i in graph[v]: if (i != parent): dfs(i, v) for j in range(1, k + 1): res += vertex_count[i][j - 1] * vertex_count[v][k - j] for j in range(1, k + 1): vertex_count[v][j] += vertex_count[i][j - 1] k = 2 insert_edge(1, 2) insert_edge(2, 3) insert_edge(3, 4) insert_edge(2, 5) dfs(1, 0) print(res)
輸入
k = 2 insert_edge(1, 2) insert_edge(2, 3) insert_edge(3, 4) insert_edge(2, 5)
輸出
4
更新於：2020年8月27日
195 次瀏覽
廣告