Question

1857. 有向图中最大颜色值

English Version

题目描述

给你一个 有向图 ，它含有 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.length
• m == edges.length
• 1 <= n <= 105
• 0 <= m <= 105
• colors 只含有小写英文字母。
• 0 <= aj, bj < n

解法

方法一：拓扑排序 + 动态规划

求出每个点的入度，进行拓扑排序。每个点维护一个长度为 $26$ 的数组，记录每个字母从任意起点到当前点的出现次数。

时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。

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 ans

class 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
}