LeetCode - 1857. Largest Color Value in a Directed Graph

Hard

1857. Largest Color Value in a Directed Graph

題目

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the ith node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [, ] indicates that there is a directed edge from node to node .

A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from to for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a".

Example 2

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints

• n == colors.length
• m == edges.length
• 1 <= n <=
• 0 <= m <=
• colors consists of lowercase English letters.
• 0 <= , < n

解題思路

這題是 有向圖 + DP，並且需要先確認圖中 不能有環

• 使用 Topological Sort（Kahn’s Algorithm）

  • 若最後無法走訪所有節點，代表圖中有環，直接回傳 -1

• DP 定義：

  • dp[u][c]：走到節點 u 時，顏色 c 出現的最大次數
  • 共有 26 種顏色

• 建圖與入度：

  • graph[u]：u 能走到哪些節點
  • indeg[v]：有幾條邊指向 v

• 初始化：

  • 所有 indeg == 0 的節點都可以當起點，放入 queue

• Topological Sort 過程：

  • 每處理一個節點 u
    • 將 u 自己的顏色次數加一
      dp[u][colors[u] - 'a']++
    • 更新答案
  • 對於每一條邊 u -> v
    • 所有能走到 u 的最佳路徑，都可以延伸到 v
    • 對所有顏色：
      • dp[v][c] = max(dp[v][c], dp[u][c])
    • 更新 indeg[v]
    • 若 indeg[v] == 0，放入 queue

• 若最後走訪的節點數量不等於 n

  • 代表存在 cycle，回傳 -1

Solution Code

Time Complexity
O(n + m) × 26

Space Complexity
O(n × 26)

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> graph(n); // u 能走到誰
        vector<int> indeg(n, 0); // (入度) v 有幾條邊指進來

        // 建圖
        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            indeg[e[1]]++;
        }

        // Kahn’s Algorithm，q 紀錄起點
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) q.push(i); // 所有 入度為 0 的點 都可以當起點
        }

        int ans = 0;
        int visited = 0;
        vector<vector<int>> dp(n, vector<int>(26, 0)); // 26 種顏色

        // Topological Sort
        while (!q.empty()) {
            int u = q.front(); 
            q.pop();
            visited++;

            int color = colors[u] - 'a';
            dp[u][color]++; // 走到節點 u，它自己的顏色出現一次

            ans = max(ans, dp[u][color]);

            // u → v 
            for (int v : graph[u]) { // 對 所有 u 能走到的節點 v
                for (int c = 0; c < 26; c++) {
                    // 所有能走到 u 的最佳路徑，都可以延伸到 v
                    // u 累積到的所有顏色次數，都可以當成 v 的候選答案
                    // dp[v][c]: 原本的 dp[v][c]
                    // dp[u][c]: 從 u 來的 dp[u][c]
                    dp[v][c] = max(dp[v][c], dp[u][c]);
                }

                // indeg[v]: 還有幾個前置節點沒處理
                indeg[v]--; // u 已經處理完
                if (indeg[v] == 0) q.push(v); // v 的所有前置節點都處理完了，現在 v 可以進 queue
            }

        }
        if (visited != n) return -1; // vis 超過 n 次代表有環
        return ans;
    }
};