Skip to content

LeetCode: 1857-Largest Color Value in a Directed Graph 解題紀錄

Last Updated on 2023-04-09 by Clay

題目

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] = [aj, bj] indicates that there is a directed edge from node aj to node bj.

A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+1 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" (red in the above image).

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 <= 105
  • 0 <= m <= 105
  • colors consists of lowercase English letters.
  • 0 <= aj, bj < n

題目給定一個路徑，路徑上的每個節點都有對應的顏色，也有節點的有向連接列表。我們要找到一條有效的路徑（意即沒有迴圈的向前路徑），其路徑的顏色分數為該條路徑上最常出現的顏色的出現次數。最終我們回傳的，是所有有效路徑中顏色分數最高者的分數。

而如果有向圖中存在著迴圈，如 example 2，則返回 -1。

解題思路

在這個問題中，我們需要找到給定有向圖中任何有效路徑的最大顏色值，或者在圖中包含循環時返回 -1。為了解決這個問題，我們可以使用動態規劃和拓撲排序的組合。

以下是解題步驟：

  1. 初始化變量：建立一個鄰接矩陣 adj 來存儲有向圖的邊；建立一個陣列 indegree 來存儲每個節點的入度；建立一個二維陣列 dp 來存儲每個節點的顏色計數。
  2. 遍歷所有的邊，將邊的信息存儲到鄰接矩陣 adj 中，並更新每個節點的入度。
  3. 對於入度為 0 的節點，將它們添加到佇列 q 中，並在 dp 中將對應顏色的計數初始化為 1。
  4. 定義一個變量 ans 來存儲最大顏色值，以及一個變量 cnt 來計數已經訪問過的節點。
  5. 當佇列 q 不為空時，從 q 中取出一個節點 u，將已訪問節點計數 cnt 增加 1，並更新 ans 的值。
  6. 遍歷 u 的所有相鄰節點 v，對於每個 v 和顏色 i，根據顏色是否相同來更新 dp[v][i] 的值。然後將節點 v 的入度減 1，如果入度變為 0，則將節點 v 添加到佇列 q 中。
  7. 最後，如果訪問過的節點數量 cnt 等於 n，則返回 ans；否則返回 -1，表示圖中存在循環。


C++ 範例程式碼

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();

        // `adj` save edges of directed graph
        vector<vector<int>> adj(n);
        
        // `indegree` save indegree of nodes
        vector<int> indegree(n, 0);

        // Traversal, then save the connected edge and indegree
        for (auto& edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            ++indegree[edge[1]];
        }

        // Initialize a `dp` array to store the color label (a to z are 26 letters)
        vector<vector<int>> dp(n, vector<int>(26, 0));
        vector<int> q;
        for (int i=0; i<n; ++i) {
            if (indegree[i] == 0) {
                q.push_back(i);
                dp[i][colors[i]-'a'] = 1;
            }
        }

        // If `q` is not empty, pick up `u` in top of `q` and update the `dp` with its connect node `u` 
        int ans = 0;
        int cnt = 0;
        while (!q.empty()) {
            // Get the top of `q`
            int u = q.back();
            q.pop_back();

            // Add 1 to cnt
            ++cnt;

            for (int v: adj[u]) {
                // Update `dp`
                for (int i=0; i<26; ++i) {
                    int val = (i == colors[v]-'a') ? dp[u][i]+1 : dp[u][i];
                    dp[v][i] = max(dp[v][i], val);
                }

                // If in-degree is equal to 0, add it to `q` and will be started a new counting
                if (--indegree[v] == 0) {
                    q.push_back(v);
                }
            }

            // Set `ans` to the current maximum value of `dp`
            ans = max(ans, *max_element(dp[u].begin(), dp[u].end()));
        }

        // If not loop, return `ans`
        return cnt == n ? ans : -1;
    }
};



Python 範例程式碼

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)

        # `adj` save edges of directed graph
        adj = [[] for _ in range(n)]
        
        # `indegree` save indegree of nodes
        indegree = [0] * n

        # Traversal, then save the connected edge and indegree
        for edge in edges:
            adj[edge[0]].append(edge[1])
            indegree[edge[1]] += 1

        # Initialize a `dp` array to store the color label (a to z are 26 letters)
        dp = [[0] * 26 for _ in range(n)]
        q = []
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
                dp[i][ord(colors[i])-ord('a')] = 1

        # If `q` is not empty, pick up `u` in top of `q` and update the `dp` with its connect node `u` 
        ans = 0
        cnt = 0
        while q:
            # Get the top of `q`
            u = q.pop()

            # Add 1 to cnt
            cnt += 1

            for v in adj[u]:
                # Update `dp`
                for i in range(26):
                    val = dp[u][i] + 1 if i == ord(colors[v])-ord('a') else dp[u][i]
                    dp[v][i] = max(dp[v][i], val)

                # If in-degree is equal to 0, and node to `q` and will be started a new counting
                indegree[v] -= 1
                if (indegree[v] == 0):
                    q.append(v)

            # Set `ans` to the current maximum value of `dp`
            ans = max(ans, max(dp[u]))

        # If not loop, return `ans`
        return ans if cnt == n else -1

References

Read More

Tags:

Leave a Reply