鏈接：https://leetcode-cn.com/problems/find-eventual-safe-states/
package leetcode
func EventualSafeNodes(graph [][]int) []int {
flag := make([]int, len(graph)+1, len(graph)+1) //遍歷過的標(biāo)記列表,初始化為0,-1為非安全點,1為安全點
var list []int
var deep func(num int) bool
deep = func(num int) bool {
if flag[num] == -1 {
return false
}
if flag[num] == 1 {
return true
}
if len(graph[num]) == 0 {
flag[num] = 1
return true
}
for _, n := range list[0 : len(list)-1] {
if n == num {
flag[num] = -1
return false
}
}
safe := true
for j := 0; j < len(graph[num]); j++ {
list = append(list, graph[num][j])
is := deep(graph[num][j])
list = list[0 : len(list)-1]
if !is {
safe = false
break
}
}
if safe {
flag[num] = 1
return true
}
flag[num] = -1
return false
}
var rtn []int
for i := 0; i < len(graph); i++ {
list = append(list, i)
safe := deep(i)
if safe {
rtn = append(rtn, i)
}
list = list[0 : len(list)-1]
}
return rtn
}
