本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個(gè)?有向圖?，它含有?n?個(gè)節(jié)點(diǎn)和?m?條邊。節(jié)點(diǎn)編號從?0?到?n - 1?。

給你一個(gè)字符串?colors?，其中?colors[i]?是小寫英文字母，表示圖中第?i?個(gè)節(jié)點(diǎn)的?顏色?（下標(biāo)從?0?開始）。同時(shí)給你一個(gè)二維數(shù)組?edges?，其中?edges[j] = [aj, bj]?表示從節(jié)點(diǎn)?aj?到節(jié)點(diǎn)?bj?有一條?有向邊?。

圖中一條有效?路徑?是一個(gè)點(diǎn)序列?x1 -> x2 -> x3 -> ... -> xk?，對于所有?1 <= i < k?，從?xi?到?xi+1?在圖中有一條有向邊。路徑的?顏色值?是路徑中?出現(xiàn)次數(shù)最多?顏色的節(jié)點(diǎn)數(shù)目。

請你返回給定圖中有效路徑里面的?最大顏色值?。 如果圖中含有環(huán)，請返回?-1?。

示例 1：

輸入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
輸出：3
解釋：路徑 0 -> 2 -> 3 -> 4 含有 3 個(gè)顏色為 "a" 的節(jié)點(diǎn)（上圖中的紅色節(jié)點(diǎn)）。

示例 2：

輸入：colors = "a", edges = [[0,0]]
輸出：-1
解釋：從 0 到 0 有一個(gè)環(huán)。

提示：

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

解法 拓?fù)渑判?+ 動態(tài)規(guī)劃

我們需要求出的答案等價(jià)于：對于一種顏色 $c$ ，以及一條路徑 $\text{path}$ ，其中顏色為 $c$ 的節(jié)點(diǎn)有 ${\text{path}}_c$ 個(gè)。我們希望挑選 $c$ 以及 $path$ ，使得 ${\text{path}}_c$ 的值最大。

我們可以枚舉顏色 $c$ ，隨后選出可以使得 ${\text{path}}_c$ 達(dá)到最大值的 $\text{path}$ 。這些 ${\text{path}}_c$ 中的最大值即為答案。

• 如果給定的有向圖包含環(huán)，那么它不存在拓?fù)渑判颉?/li>
• 如果給定的有向圖不包含環(huán)，那么這個(gè)有向圖是一個(gè)「有向無環(huán)圖」，它一定存在拓?fù)渑判颉?br> 根據(jù)拓?fù)渑判虻男再|(zhì)，如果節(jié)點(diǎn) $a$ 有一條有向邊指向節(jié)點(diǎn) $b$ ，那么 $b$ 在拓?fù)渑判蛑幸欢ǔ霈F(xiàn)在 $a$ 之后。因此，一條有效路徑上點(diǎn)的順序與它們在拓?fù)渑判蛑谐霈F(xiàn)的順序是一致的。

我們可以根據(jù)拓?fù)渑判騺磉M(jìn)行動態(tài)規(guī)劃。設(shè) $dp[v][c]$ 表示以節(jié)點(diǎn) $v$ 為終點(diǎn)的所有有效路徑中，包含顏色 $c$ 的節(jié)點(diǎn)數(shù)量的最大值。在進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，我們考慮所有 $v$ 的前驅(qū)節(jié)點(diǎn)（即有一條有向邊指向 $v$ 的節(jié)點(diǎn)）${\text{prev}}_v$
?$$dp[v][c]=\left(\underset{u\in {\text{prev}}_j}{\max }dp[u][c]\right)+\mathbb{I}(v,c)$$
即找出前驅(qū)節(jié)點(diǎn)中包含顏色 $c$ 的節(jié)點(diǎn)數(shù)量最多的那個(gè)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移，并且如果 $v$ 本身的顏色為 $c$ ，$dp[v][c]$ 的值就增加 $1$ 。這里 $\mathbb{I}(v,c)$ 為示性函數(shù)，當(dāng)節(jié)點(diǎn) $v$ 的顏色為 $c$ 時(shí)，函數(shù)值為 $1$ ，否則為 $0$ 。那么 ${\text{path}}_c$ 的最大值即為 $dp[v][c]$ 中的最大值。

我們可以將狀態(tài)轉(zhuǎn)移，融入使用廣度優(yōu)先搜索的方法求解拓?fù)渑判虻倪^程中。當(dāng)遍歷到節(jié)點(diǎn) $u$ 時(shí)：

• 如果 $u$ 的顏色為 $c$ ，那么將 $dp[u][c]$ 的值增加 $1$ ；
• 枚舉 $u$ 的所有后繼節(jié)點(diǎn)（即從 $u$ 出發(fā)經(jīng)過一條有向邊可以到達(dá)的節(jié)點(diǎn)），對于后繼節(jié)點(diǎn) $v$ ，將 $dp[v][c]$ 更新為其與 $dp[u][c]$ 的較大值。

這樣的操作與上文描述的狀態(tài)轉(zhuǎn)移方程是一致的。它的好處在于，如果使用廣度優(yōu)先搜索的方法求解拓?fù)渑判?，那么我們需要使用鄰接表存儲所有的有向邊，而上文的動態(tài)規(guī)劃是通過「枚舉 $v\to$ 枚舉前驅(qū)節(jié)點(diǎn) $u$ 」進(jìn)行狀態(tài)轉(zhuǎn)移的，這就需要我們額外存儲所有邊的反向邊，才能通過 $v$ 找到所有的前驅(qū)節(jié)點(diǎn)。如果我們通過「枚舉 $u\to$ 枚舉后繼節(jié)點(diǎn) $v$ 」進(jìn)行狀態(tài)轉(zhuǎn)移，這樣就與拓?fù)渑判虼鎯Φ倪叡３忠恢?/strong>了。

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<int> g[n];
        vector<int> ind(n); // 節(jié)點(diǎn)的入度統(tǒng)計(jì)，用于找出拓?fù)渑判蛑凶铋_始的節(jié)點(diǎ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']; // 節(jié)點(diǎn)u對應(yīng)的顏色+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;
    }
};