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.lengthm == edges.length1 <= n <= 1050 <= m <= 105colorsconsists of lowercase English letters.0 <= aj, bj < n
題目給定一個路徑，路徑上的每個節點都有對應的顏色，也有節點的有向連接列表。我們要找到一條有效的路徑（意即沒有迴圈的向前路徑），其路徑的顏色分數為該條路徑上最常出現的顏色的出現次數。最終我們回傳的，是所有有效路徑中顏色分數最高者的分數。
而如果有向圖中存在著迴圈，如 example 2，則返回 -1。
解題思路
在這個問題中，我們需要找到給定有向圖中任何有效路徑的最大顏色值，或者在圖中包含循環時返回 -1。為了解決這個問題，我們可以使用動態規劃和拓撲排序的組合。
以下是解題步驟：
- 初始化變量：建立一個鄰接矩陣
adj來存儲有向圖的邊；建立一個陣列indegree來存儲每個節點的入度；建立一個二維陣列dp來存儲每個節點的顏色計數。 - 遍歷所有的邊，將邊的信息存儲到鄰接矩陣
adj中，並更新每個節點的入度。 - 對於入度為 0 的節點，將它們添加到佇列
q中，並在dp中將對應顏色的計數初始化為 1。 - 定義一個變量
ans來存儲最大顏色值，以及一個變量cnt來計數已經訪問過的節點。 - 當佇列
q不為空時，從q中取出一個節點u，將已訪問節點計數cnt增加 1，並更新ans的值。 - 遍歷
u的所有相鄰節點v，對於每個v和顏色i，根據顏色是否相同來更新dp[v][i]的值。然後將節點v的入度減 1，如果入度變為 0，則將節點v添加到佇列q中。 - 最後，如果訪問過的節點數量
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