好久没发每日
周赛也没有发
不过我每周都有比
就懒得发而已
我最近没加啥分
卡1900
我哭了
题目:
有一张图
如果有环就回传-1
不然就回传图上面所有路径中最强的颜色
最强的颜色 = 某条路径出现最多次的颜色
思路:
用bfs+indeg
好像叫啥khan的算法
反正就是可以依照顺序遍历有向图
同时用阵列dp记录
这样可以顺便检测环
这个最强的颜色用讲的有点难说
假设两个路径
1 : aaaabaaaaabbbbbb
2 : bbbb
虽然全部的话是b比较多 (11
但是a在路径1出现9次 这才是最多次
9才是答案
用这个想的话
就会发现每条路径彼此根本就没差
但是如果要找路径最常出现的颜色
那就要记26种颜色
这样又会有一个问题
假设路径1跟2都到节点a
路径1有三个a
路径b有三个b
那这样我不知道选哪个比较好
所以我是假设每个颜色都是当前最多的
每次bfs都会只看那个颜色
这样某个路径出现最多次的话就更新答案
那个颜色一定是真的最多次
不然他就不会是最多次
会被其他颜色替代
对ㄚ
```cpp
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges)
{
int n = colors.size();
int m = edges.size();
int res = 0;
queue<int> q;
unordered_map<int,vector<int>> path;
vector<int> indeg_(n);
for(vector<int> k : edges)
{
path[k[0]].push_back(k[1]);
indeg_[k[1]] ++;
}
for(int i = 0 ; i < n ; i ++)
{
if(indeg_[i] == 0)
{
q.push(i);
}
}
for(int i = 0 ; i < 26 ; i ++)
{
vector<int> paper(n,0);
vector<int> indeg = indeg_;
queue<int> qq = q;
while(!qq.empty())
{
int now = qq.front();
qq.pop();
if(colors[now]-'a' == i)paper[now] ++;
for(int nxt : path[now])
{
indeg[nxt]

大师

养我

赞。