今日题目

https://leetcode.com/problems/find-eventual-safe-states/description/

注意

出边指的是该节点的任意一条边，包括自环。

思路

唯一的终止节点是没有出边的节点。

然后我们需要找出哪些节点连向这些终止节点。

因此，可以使用递归（或任何 LIFO 算法）来解决这道题。

方法

  • 使用 DFS。
  • 如果找到一个没有出边的节点，则它是终止节点。
  • 如果发现自环，环中所有节点均不安全。
  • 如果一个节点只连向安全节点，则它本身也是安全的。

复杂度

  • 时间复杂度：$O(N)$，每个节点只会被访问一次。
  • 空间复杂度：$O(N)$。

代码


class Solution:

    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:

        n = len(graph)

        safety = [-1] * n

        vis = [0] * n

        ans = []


        def dfs(x):

            if safety[x] != -1:

                return safety[x]

            if vis[x] == 1:

                safety[x] = 0

                return 0

            vis[x] = 1

            if len(graph[x]) == 0:

                safety[x] = 1

                return 1


            res = 0


            for to in graph[x]:

                res += dfs(to)


            if res == len(graph[x]):

                safety[x] = 1

            else:

                safety[x] = 0

            return safety[x]


        for i in range(n):

            if(dfs(i) == 1):

                ans.append(i)


        return ans