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
}

大師