題目描述: 給定一個有向圖,n 個節點各有一個顏色(用小寫字母表示)。求所有合法路徑中,單一顏色出現次數的最大值。若圖中有環,回傳 -1。
解題思路: 拓撲排序 + DP。
dp[u][c] = 所有到達節點 u 的路徑中,顏色 c 出現的最大次數。dp[v][c] = max(dp[v][c], dp[u][c])。處理完所有入邊後,dp[v][colors[v]] += 1(加上自身顏色)。dp[u][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 answerDFS + 記憶化 O((n+E)×26):用 DFS 從每個未訪問節點出發,三色標記偵測環,記憶化計算每個節點的最大顏色計數。本質相同但用遞迴棧,深度大時可能棧溢出。
暴力枚舉路徑:枚舉所有路徑並統計顏色。路徑數量可能指數級,完全不可行。