【Leetcode】1857. Largest Color Value in a Directed Graph

题目地址：

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

给定给一个n nn个顶点的无权有向图，每个顶点有个颜色。一条路径的颜色数定义为其所有顶点里，颜色使用频率最高的那个颜色的使用频率。问所有路径中，颜色数最大是多少。如果有环则返回− 1 -1−1。

设f [ u ] [ c ] f[u][c]f[u][c]是以u uu结尾的所有路径中c cc的最高频率。由于同一个路径，如果起点能延伸的话，对于每个颜色的频率都有可能增长，所以我们肯定希望路径越长越好。我们考虑用拓扑排序来做，在分层图上做递推，显然当u uu的颜色不为c cc时，f [ u ] [ c ] = max ⁡ v → u { f [ v ] [ c ] } f[u][c]=\max_{v\to u} \{f[v][c]\}f[u][c]=maxv→u​{f[v][c]}；否则f [ u ] [ c ] = 1 + max ⁡ v → u { f [ v ] [ c ] } f[u][c]=1+\max_{v\to u} \{f[v][c]\}f[u][c]=1+maxv→u​{f[v][c]}。同时拓扑排序还需要记录有没有环。如果没有环的话，最终答案就是max ⁡ u , c f [ u ] [ c ] \max_{u,c} f[u][c]maxu,c​f[u][c]。代码如下：

classSolution{public:intlargestPathValue(string&col,vector<vector<int>>&es){intn=col.size(),m=es.size();vector<int>h(n,-1),e(m),ne(m),ind(n);intidx=0;autoadd=[&](inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx++;};for(auto&e:es){add(e[0],e[1]);ind[e[1]]++;}vector<array<int,26>>cnt(n,array<int,26>{});queue<int>q;for(inti=0;i<n;i++)if(!ind[i])q.push(i);intres=0,vis_cnt=0;while(q.size()){intu=q.front();q.pop();vis_cnt++;intcu=col[u]-'a';cnt[u][cu]++;res=max(res,cnt[u][cu]);for(inti=h[u];~i;i=ne[i]){intv=e[i],cv=col[v]-'a';for(intc=0;c<26;c++)cnt[v][c]=max(cnt[v][c],cnt[u][c]);if(!--ind[v])q.push(v);}}returnvis_cnt==n?res:-1;}};

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