力扣 有向图中最大颜色值

https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/submissions/

我自己的解法，记忆化搜索
rec[i]记录以i为起点的路径，所有颜色的最大值

class Solution {
public:
    int n;

    int idx = 0;
    vector<int> head;
    vector<bool> vis1;
    vector<bool> vis2;
    struct {
        int nxt, to;
    } es[100005];
    vector<vector<int> > rec;
    int cnt[26] = {0};
    int ans = 0;

    vector<int> dfs(int i, int s, string &color) {
        if (vis1[i]) {
            ans = -1;
            return vector<int>(26, 0);
        }

        if (vis2[i]) {
            return rec[i];
        }

        vis1[i] = true;

        for (int e = head[i]; e != -1; e = es[e].nxt) {
            vector<int> ret = dfs(es[e].to, s, color);
            for (int k = 0; k < 26; ++k) {
                rec[i][k] = max(rec[i][k], ret[k]);
            }
        } 

        ++rec[i][color[i] - 'a'];


        vis1[i] = false;
        vis2[i] = true;

        return rec[i];
    }

    int largestPathValue(string colors, vector<vector<int>>& edges) {
       int n = colors.length();

       head.resize(n, -1);
       vis1.resize(n, false);
       vis2.resize(n, false);
       rec.resize(n, vector<int>(26, 0));

       for (auto &e : edges) {
           es[++idx].to = e[1];
           es[idx].nxt = head[e[0]];
           head[e[0]] = idx;
       }

        for (int i = 0; i < n; ++i) {
            dfs(i, i, colors);
            if (ans == -1) {
                return -1;
            }

            for (int k = 0; k < 26; ++k) {
                ans = max(rec[i][k], ans);
            }
        }

        return ans;
    }
};

拓扑排序加dp

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&& edge: edges) {
            ++indeg[edge[1]];
            g[edge[0]].push_back(edge[1]);
        }

        // 记录拓扑排序过程中遇到的节点个数
        // 如果最终 found 的值不为 n，说明图中存在环
        int found = 0;
        vector<array<int, 26>> f(n);
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (!indeg[i]) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            ++found;
            int u = q.front();
            q.pop();
            // 将节点 u 对应的颜色增加 1
            ++f[u][colors[u] - 'a'];
            // 枚举 u 的后继节点 v
            for (int v: g[u]) {
                --indeg[v];
                // 将 f(v,c) 更新为其与 f(u,c) 的较大值
                for (int c = 0; c < 26; ++c) {
                    f[v][c] = max(f[v][c], f[u][c]);
                }
                if (!indeg[v]) {
                    q.push(v);
                }
            }
        }

        if (found != n) {
            return -1;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, *max_element(f[i].begin(), f[i].end()));
        }
        return ans;
    }
};


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/solution/you-xiang-tu-zhong-zui-da-yan-se-zhi-by-dmtaa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。