HardRating 2313

1857. Largest Color Value in a Directed Graph

hash-tablestringdynamic-programminggraphtopological-sortmemoizationcounting

在 LeetCode 上作答 ↗

解題說明

Largest Color Value in a Directed Graph

題目描述：給定一個有向圖，n 個節點各有一個顏色（用小寫字母表示）。求所有合法路徑中，單一顏色出現次數的最大值。若圖中有環，回傳 -1。

解題思路：拓撲排序 + DP。

環偵測：使用 Kahn's 算法（BFS 拓撲排序），若最終處理的節點數 < n，表示有環。
DP 定義：dp[u][c] = 所有到達節點 u 的路徑中，顏色 c 出現的最大次數。
轉移：按拓撲序處理。對於邊 (u, v)：dp[v][c] = max(dp[v][c], dp[u][c])。處理完所有入邊後，dp[v][colors[v]] += 1（加上自身顏色）。
答案為所有 dp[u][c] 的最大值。

C++ 解法

複雜度分析

時間複雜度：O((n + E) × 26) — 拓撲排序遍歷所有節點和邊，每條邊更新 26 個顏色計數。簡化為 O(n + E)。

空間複雜度：O(n × 26 + E) = O(n + E) — DP 表格 O(26n)，鄰接表 O(E)。

虛擬碼

1. Build adjacency list and compute in-degrees
2. Initialize dp[u][c] = 0 for all u, c
3. Enqueue all nodes with in-degree 0; set dp[u][colors[u]] = 1 for these
4. BFS (Kahn's algorithm):
   a. Dequeue node u, increment processed count
   b. Update global answer with max of dp[u][0..25]
   c. For each neighbor v of u:
      - For each color c: dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v]==c ? 1 : 0))
      - Decrement in-degree of v; if 0, enqueue v
5. If processed < n, return -1 (cycle exists)
6. Return answer

其他解法

DFS + 記憶化 O((n+E)×26)：用 DFS 從每個未訪問節點出發，三色標記偵測環，記憶化計算每個節點的最大顏色計數。本質相同但用遞迴棧，深度大時可能棧溢出。

暴力枚舉路徑：枚舉所有路徑並統計顏色。路徑數量可能指數級，完全不可行。

延伸思考

如果每個節點可以有多個顏色，如何修改 DP 狀態？
如果要求的是路徑上「不同顏色數量」的最大值，該如何解決？
如果圖是動態的（不斷加邊），如何增量式地更新答案？

Largest Color Value in a Directed Graph — CaffeCode