好久沒發每日
週賽也沒有發
不過我每週都有比
就懶得發而已
我最近沒加啥分
卡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]

大師

養我

讚。