資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：在有向圖中查詢最大顏色值
假設我們有一個包含 n 個彩色節點和 m 個不同邊的有向圖。節點編號從 0 到 n-1。我們有一個字串 col，其中包含小寫字母，col[i] 表示該圖中第 i 個節點的顏色（從 0 開始索引）。我們還有一個邊列表，其中 edges[j] = (u, v) 表示 u 和 v 之間有一條邊。
圖中的一條有效路徑是從 1 到 k 的所有 i 的節點 xi 序列，使得從 xi 到 xi+1 存在一條有向邊。路徑的顏色是該路徑中最常出現的節點顏色。我們必須找到該圖中任何有效路徑的最大顏色值。如果圖中存在迴圈，則返回 -1。
因此，如果輸入類似於 col = "aabada" edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]，
則輸出將為 4，因為 0 -> 1 -> 2 -> 3 -> 5 具有顏色為 'a' 的最長路徑。
為了解決這個問題，我們將遵循以下步驟：
n := col 的大小
graph := 從邊列表得到的給定圖
indegree := 包含節點及其入度值的對映
queue := 一個新的列表
dp := 建立一個大小為 n x 26 的陣列，並用 0 填充
colorvalues := 建立一個列表，其中包含 col 中所有 c 按字母順序排列的順序
對於 u 從 0 到 n - 1，執行以下操作：
如果 u 不在 indegree 中，則
將 u 插入到佇列的末尾
dp[u, colorvalues[u]] := 1
visited := 0
當佇列不為空時，執行以下操作：
u := 佇列的第一個元素，並將其刪除
visited := visited + 1
對於 graph[u] 中的每個 v，執行以下操作：
對於 c 從 0 到 25，執行以下操作：
dp[v, c] = dp[v, c] 和 (dp[u, c] + (如果 c 與 colorvalues[v] 相同，則為 1，否則為 0)) 的最大值
indegree[v] := indegree[v] - 1
如果 indegree[v] 等於 0，則
將 v 插入到佇列的末尾
刪除 indegree[v]
如果 visited < n，則
返回 -1
返回 dp 中的最大元素
示例
讓我們看看以下實現以獲得更好的理解
from collections import defaultdict
def solve(col, edges):
n=len(col)
graph=defaultdict(list)
indegree=defaultdict(int)
for u,v in edges:
graph[u].append(v)
indegree[v]+=1
queue=[]
dp=[[0]*26 for _ in range(n)]
colorvalues=[ord(c)-ord("a") for c in col]
for u in range(n):
if u not in indegree:
queue.append(u)
dp[u][colorvalues[u]]=1
visited=0
while queue:
u=queue.pop()
visited+=1
for v in graph[u]:
for c in range(26):
dp[v][c]=max(dp[v][c],dp[u][c] + (c==colorvalues[v]))
indegree[v]-=1
if indegree[v]==0:
queue.append(v)
del indegree[v]
if visited<n:
return -1
return max(max(x) for x in dp)
col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))輸入
"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
輸出
4
284 次檢視
