Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
推 deatheo: 大師