Today’s problem

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

Note

Outgoing edges means any edge of this point, even if this point connects to itself.

Intuition

The only points that are terminate are the points that have no edges.

Then we have to find which point connect to these terminate points.

Therefore, we can use recursive (or any LIFO algorithms) to solve this question.

Approach

  • Use a DFS.
  • If we find a point that has no outgoing edges, then its a terminate point.
  • If we find a self-loop, all points in the loop are not safety.
  • If a point only connects to safty points, then it is safety.

Complexity

  • Time complexity: $O(N)$, all points will be visited only once.
  • Space complexity: $O(N)$.

Code


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