写一下每日来骗个p币
1857. Largest Color Value in a Directed Graph
题目
在一个有向图中有n个点m条边
每个点都有一个颜色
定义color value为一个path中最常出现的color的出现次数
请问在这个图中的所有path中最大的color value
如果图中有cycle则回传-1
思路:
首先找indegree为0的点，把这些点当成起点去做dfs
接着每个点都用一个array纪录由该点出发的所有路径每个颜色出现的最大次数
如果我们发现这个点跑过了，就可以不用跑直接去看那个array纪录的颜色次数
从起点跑完所有path就可以得到答案了
然后在过程中注意有没有cycle就好
golang code :
func largestPathValue(colors string, edges [][]int) int {
n, ans,cnt := len(colors), 0,0
paths, indegree, visited, rec := make([][]int, n), make([]int, n), make([]
bool, n), make([][26]int, n)
colorsIdx := make([]byte, n)
var dfs func(node int, chk []bool) bool
dfs = func(node int, chk []bool) bool {
if chk[node] {
return true
}
chk[node] = true
if len(paths[node]) == 0 {
rec[node][int(colorsIdx[node]-'a')]++
chk[node] = false
return false
}
for _, val := range paths[node] {
if !visited[val] {
if dfs(val, chk) {
return true
}
cnt++
visited[val] = true
}
for i := 0; i < 26; i++ {
rec[node][i] = max(rec[node][i], rec[val][i])
}
}
rec[node][int(colorsIdx[node]-'a')]++
chk[node] = false
return false
}
for i := 0; i < n; i++ {
colorsIdx[i] = byte(colors[i])
}
for _, path := range edges {
from, to := path[0], path[1]
indegree[to]++
paths[from] = append(paths[from], to)
}
starts := []int{}
for key, val := range indegree {
if val == 0 {
starts = append(starts, key)
}
}
for _, val := range starts {
chk := make([]bool, n)
if !visited[val] {
hasCycle := dfs(val, chk)
if hasCycle {
return -1
}
cnt++
visited[val] = true
}
for i := 0; i < 26; i++ {
ans = max(ans, rec[val][i])
}
}
if cnt != n{return -1}
return ans
}

别卷了