802. Find Eventual Safe States

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

Python

DFS

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        safe = {}
        ans = []

        def dfs(i):
            if i in safe:
                return safe[i]

            safe[i] = False
            for nei in graph[i]:
                if not dfs(nei):
                    return safe[i]
            safe[i] = True
            return True

        for i in range(len(graph)):
            if dfs(i):
                ans.append(i)
        return ans