有向图中最大颜色值

标签: 图 拓扑排序 记忆化搜索 哈希表 动态规划 计数

难度: Hard

给你一个 有向图 ，它含有 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

Submission

运行时间: 1268 ms

内存: 52.4 MB

from collections import deque
from typing import List


class Solution:
    def typology(self, n: int, graph: List[List[int]]) -> List[int]:
        ind = [0] * n
        for start, adj_arr in enumerate(graph):
            for adj in adj_arr:
                ind[adj] += 1
        q = deque()
        for i, d in enumerate(ind):
            if d == 0:
                q.append(i)
        ans = []
        while q:
            node = q.popleft()
            ans.append(node)
            for adj in graph[node]:
                ind[adj] -= 1
                if ind[adj] == 0:
                    q.append(adj)
        return ans if len(ans) == n else []

    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        if not n:
            return 0
        graph = [[] for _ in range(n)]
        for start, end in edges:
            graph[start].append(end)
        sorted_nodes = self.typology(n, graph)
        if not sorted_nodes:
            return -1

        ans = 0
        for color in set(colors):
            fn = [0] * n
            for i in range(n):
                node_id = sorted_nodes[i]
                if colors[node_id] == color:
                    fn[node_id] = fn[node_id] + 1
                for adj in graph[node_id]:
                    fn[adj] = max(fn[adj], fn[node_id])
            ans = max(ans, *fn)
        return ans


# print(Solution().largestPathValue(
#     "eeyyeeyeye", [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [4, 6], [5, 7], [6, 8], [8, 9]]))

Explain

此题解首先通过拓扑排序检测有向图中是否存在环。如果存在环，则无法找到一个有效的顺序来处理节点，返回-1。使用拓扑排序后的节点序列，通过动态规划的方法计算各个路径的最大颜色值。对每种颜色，维护一个数组记录到达每个节点时该颜色的最大计数。遍历节点时，更新这些计数，并在所有子节点传播当前节点的颜色值计数。最终，对所有颜色进行扫描，找到出现次数最多的颜色的节点数目。

时间复杂度: O(n + m + n * c)

空间复杂度: O(n + m + n * c)

from collections import deque
from typing import List

class Solution:
    def typology(self, n: int, graph: List[List[int]]) -> List[int]:
        ind = [0] * n  # 存储每个节点的入度
        for start, adj_arr in enumerate(graph):
            for adj in adj_arr:
                ind[adj] += 1
        q = deque()
        for i, d in enumerate(ind):
            if d == 0:
                q.append(i)
        ans = []
        while q:
            node = q.popleft()
            ans.append(node)
            for adj in graph[node]:
                ind[adj] -= 1
                if ind[adj] == 0:
                    q.append(adj)
        return ans if len(ans) == n else []

    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        if not n:
            return 0
        graph = [[] for _ in range(n)]
        for start, end in edges:
            graph[start].append(end)
        sorted_nodes = self.typology(n, graph)
        if not sorted_nodes:
            return -1

        ans = 0
        for color in set(colors):
            fn = [0] * n  # 记录到达每个节点时该颜色的最大计数
            for i in range(n):
                node_id = sorted_nodes[i]
                if colors[node_id] == color:
                    fn[node_id] = fn[node_id] + 1
                for adj in graph[node_id]:
                    fn[adj] = max(fn[adj], fn[node_id])  # 更新邻接节点的颜色计数
            ans = max(ans, *fn)
        return ans

# Example usage:
# print(Solution().largestPathValue('eeyyeeyeye', [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [4, 6], [5, 7], [6, 8], [8, 9]]))

Explore

在拓扑排序过程中，如果遍历完所有节点后仍有节点的入度未归零，这意味着这些节点仍有其他节点指向它们，但这些指向它们的节点并未在拓扑排序中处理。这通常表明图中存在环，因为环内的节点相互依赖，无法达到入度为零的状态。因此，如果入度数组中存在未归零的节点，我们可以确定图中存在环。

在有向图中，如果存在环，则无法进行有效的拓扑排序，因为拓扑排序需要所有节点的依赖关系是有向无环的。在这个问题中，需要计算最大颜色值的路径，如果存在环，则可能导致某些节点在计算路径时被重复计算，从而无法确定一个清晰且合理的节点处理顺序。因此，如果图中存在环，就返回-1，表示无法计算一个有效的最大颜色值。

在动态规划中，对每种颜色维护一个独立的数组可以帮助我们准确地追踪和更新在每个节点到达时该颜色的出现次数。这种做法允许我们在遍历节点时，不仅更新当前节点的颜色计数，还能将这一计数传播到所有子节点。这种方法确保了我们能够有效地计算每条路径上特定颜色的最大累积出现次数，从而找到整个图中该颜色出现的最大次数。

在更新邻接节点的颜色计数时，我们采用了最大化策略。即对于每个邻接节点，我们检查所有可能的前置节点的颜色计数，并取其中的最大值更新到邻接节点的颜色计数中。这样可以确保即使多个前置节点拥有相同的颜色，我们也能通过取最大的颜色计数来保证计数的正确性和最大性。这种方法有效地保证了不同路径对颜色计数的最大贡献能够被考虑在内。