Re: [閒聊] 每日leetcode
802. Find Eventual Safe States
思路:
首先先記錄terminal_point
所有都terminal_point都是safe_point
接著就dfs下去
如果i以後的路徑都能到safe_point
那i就是safe_point
就把i記錄下來，並且記錄所有拜訪過的點，不要重複拜訪
golang code :
func eventualSafeNodes(graph [][]int) []int {
n := len(graph)
ans, visited, safe_pointed := []int{}, make([]bool, n), make([]bool, n)
for key, val := range graph {
if len(val) == 0 {
safe_pointed[key] = true
}
}
var dfs func(cur_node int)
dfs = func(cur_node int) {
if !visited[cur_node] {
if safe_pointed[cur_node] {
return
}
visited[cur_node] = true
has_non_safe_path := false
for _, val := range graph[cur_node] {
if !visited[val] {
dfs(val)
}
if safe_pointed[val] == false {
has_non_safe_path = true
}
}
if !has_non_safe_path {
safe_pointed[cur_node] = true
}
return
}
}
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i)
}
if safe_pointed[i] {
ans = append(ans, i)
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.38.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737733361.A.908.html
推
01/25 00:02,
10月前
, 1F
01/25 00:02, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1305 之 1552 篇)：