LeetCode 1857. Largest Color Value in a Directed Graph【拓扑排序,动态规划】困难-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 1857. Largest Color Value in a Directed Graph【拓扑排序,动态规划】困难。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个 有向图 ，它含有 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：
LeetCode 1857. Largest Color Value in a Directed Graph【拓扑排序,动态规划】困难,# 拓扑排序,动态规划,leetcode,动态规划,算法

输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点（上图中的红色节点）。

示例 2：
LeetCode 1857. Largest Color Value in a Directed Graph【拓扑排序,动态规划】困难,# 拓扑排序,动态规划,leetcode,动态规划,算法

输入：colors = "a", edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。

提示：

n == colors.length
m == edges.length
1 <= n <= 10^5
0 <= m <= 10^5
colors 只含有小写英文字母。
0 <= aj, bj < n

解法拓扑排序 + 动态规划

我们需要求出的答案等价于：对于一种颜色 $c$ ，以及一条路径 $\textit{path}$ ，其中颜色为 $c$ 的节点有 $\textit{path}_c$ 个。我们希望挑选 $c$ 以及 $p a t h$ ，使得 $\textit{path}_c$ 的值最大。

我们可以枚举颜色 $c$ ，随后选出可以使得 $\textit{path}_c$ 达到最大值的 $\textit{path}$ 。这些 $\textit{path}_c$ 中的最大值即为答案。

如果给定的有向图包含环，那么它不存在拓扑排序。
如果给定的有向图不包含环，那么这个有向图是一个「有向无环图」，它一定存在拓扑排序。
根据拓扑排序的性质，如果节点 $a$ 有一条有向边指向节点 $b$ ，那么 $b$ 在拓扑排序中一定出现在 $a$ 之后。因此，一条有效路径上点的顺序与它们在拓扑排序中出现的顺序是一致的。

我们可以根据拓扑排序来进行动态规划。设 $d p [v] [c]$ 表示以节点 $v$ 为终点的所有有效路径中，包含颜色 $c$ 的节点数量的最大值。在进行状态转移时，我们考虑所有 $v$ 的前驱节点（即有一条有向边指向 $v$ 的节点） $\textit{prev}_v$
$\left( \max_{u \in \textit{prev}_j} dp [u][c] \right) + \mathbb{I}(v, c)$
即找出前驱节点中包含颜色 $c$ 的节点数量最多的那个节点进行转移，并且如果 $v$ 本身的颜色为 $c$ ， $d p [v] [c]$ 的值就增加 $1$ 。这里 $\mathbb{I}(v, c)$ 为示性函数，当节点 $v$ 的颜色为 $c$ 时，函数值为 $1$ ，否则为 $0$ 。那么 $\textit{path}_c$ 的最大值即为 $d p [v] [c]$ 中的最大值。

我们可以将状态转移，融入使用广度优先搜索的方法求解拓扑排序的过程中。当遍历到节点 $u$ 时：

如果 $u$ 的颜色为 $c$ ，那么将 $d p [u] [c]$ 的值增加 $1$ ；
枚举 $u$ 的所有后继节点（即从 $u$ 出发经过一条有向边可以到达的节点），对于后继节点 $v$ ，将 $d p [v] [c]$ 更新为其与 $d p [u] [c]$ 的较大值。

这样的操作与上文描述的状态转移方程是一致的。它的好处在于，如果使用广度优先搜索的方法求解拓扑排序，那么我们需要使用邻接表存储所有的有向边，而上文的动态规划是通过「枚举 $v \to$ 枚举前驱节点 $u$ 」进行状态转移的，这就需要我们额外存储所有边的反向边，才能通过 $v$ 找到所有的前驱节点。如果我们通过「枚举 $\to$ 枚举后继节点 $v$ 」进行状态转移，这样就与拓扑排序存储的边保持一致了。

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<int> g[n];
        vector<int> ind(n); // 节点的入度统计，用于找出拓扑排序中最开始的节点
        for (vector<int>& e : edges) {
            g[e[0]].push_back(e[1]);
            ++ind[e[1]];
        }
        vector<array<int, 26>> dp(n);
        int found = 0, ans = 0;
        queue<int> q;
        for (int i = 0; i < n; ++i) if (ind[i] == 0) q.push(i); 
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ++found;
            ++dp[u][colors[u] - 'a']; // 节点u对应的颜色+1
            ans = max(ans, dp[u][colors[u] - 'a']);
            for (int v : g[u]) {
                for (int c = 0; c < 26; ++c)
                    dp[v][c] = max(dp[u][c], dp[v][c]);
                if (--ind[v] == 0) q.push(v);
            } 
        } 
        return found != n ? -1 : ans;
    }
};

复杂度分析：文章来源地址https://www.toymoban.com/news/detail-615588.html

时间复杂度： $|\Sigma |)$ ，其中 $|\Sigma |$ 表示颜色的数量，在本题中 $|\Sigma |=26$ 。
一般的拓扑排序需要的时间为 $O (n + m)$ 。而在本题中在拓扑排序的过程中加入了状态转移，由于一条有向边对应着 $|\Sigma |$ 次状态转移，因此拓扑排序的时间复杂度实际为 $m|\Sigma|)$ 。
空间复杂度： $O(n|\Sigma| + m)$ 。我们需要 $|\Sigma|)$ 的空间存储对应数量的状态；我们需要 $O (n + m)$ 的空间存储邻接表；我们需要 $O (n)$ 的队列空间进行拓扑排序。将它们相加，即可得到总时间复杂度为 $|\Sigma| + m)$ 。