| comments | difficulty | edit_url | rating | source | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2312 |
第 240 场周赛 Q4 |
|
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。
图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> ... -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。
示例 1：
输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点（上图中的红色节点）。
示例 2：
输入：colors = "a", edges = [[0,0]] 输出：-1 解释：从 0 到 0 有一个环。
提示：
n == colors.lengthm == edges.length1 <= n <= 1050 <= m <= 105colors只含有小写英文字母。0 <= aj, bj < n
求出每个点的入度，进行拓扑排序。每个点维护一个长度为
时间复杂度
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
indeg = [0] * n
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
indeg[b] += 1
q = deque()
dp = [[0] * 26 for _ in range(n)]
for i, v in enumerate(indeg):
if v == 0:
q.append(i)
c = ord(colors[i]) - ord('a')
dp[i][c] += 1
cnt = 0
ans = 1
while q:
i = q.popleft()
cnt += 1
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
c = ord(colors[j]) - ord('a')
for k in range(26):
dp[j][k] = max(dp[j][k], dp[i][k] + (c == k))
ans = max(ans, dp[j][k])
return -1 if cnt < n else ansclass Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length();
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
++indeg[b];
}
Deque<Integer> q = new ArrayDeque<>();
int[][] dp = new int[n][26];
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.offer(i);
int c = colors.charAt(i) - 'a';
++dp[i][c];
}
}
int cnt = 0;
int ans = 1;
while (!q.isEmpty()) {
int i = q.pollFirst();
++cnt;
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.offer(j);
}
int c = colors.charAt(j) - 'a';
for (int k = 0; k < 26; ++k) {
dp[j][k] = Math.max(dp[j][k], dp[i][k] + (c == k ? 1 : 0));
ans = Math.max(ans, dp[j][k]);
}
}
}
return cnt == n ? ans : -1;
}
}class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<vector<int>> g(n);
vector<int> indeg(n);
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].push_back(b);
++indeg[b];
}
queue<int> q;
vector<vector<int>> dp(n, vector<int>(26));
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.push(i);
int c = colors[i] - 'a';
dp[i][c]++;
}
}
int cnt = 0;
int ans = 1;
while (!q.empty()) {
int i = q.front();
q.pop();
++cnt;
for (int j : g[i]) {
if (--indeg[j] == 0) q.push(j);
int c = colors[j] - 'a';
for (int k = 0; k < 26; ++k) {
dp[j][k] = max(dp[j][k], dp[i][k] + (c == k));
ans = max(ans, dp[j][k]);
}
}
}
return cnt == n ? ans : -1;
}
};func largestPathValue(colors string, edges [][]int) int {
n := len(colors)
g := make([][]int, n)
indeg := make([]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
indeg[b]++
}
q := []int{}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 26)
}
for i, v := range indeg {
if v == 0 {
q = append(q, i)
c := colors[i] - 'a'
dp[i][c]++
}
}
cnt := 0
ans := 1
for len(q) > 0 {
i := q[0]
q = q[1:]
cnt++
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
c := int(colors[j] - 'a')
for k := 0; k < 26; k++ {
t := 0
if c == k {
t = 1
}
dp[j][k] = max(dp[j][k], dp[i][k]+t)
ans = max(ans, dp[j][k])
}
}
}
if cnt == n {
return ans
}
return -1
}