802.md

802. Find Eventual Safe States

Solution 1 (time O(n+m), space O(n))

# DFS
class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        vis = [0 for _ in range(len(graph))]

        def is_safe(cur_node):
            if vis[cur_node] != 0:
                return vis[cur_node] == 2
            vis[cur_node] = 1
            for new_node in graph[cur_node]:
                if not is_safe(new_node):
                    return False
            vis[cur_node] = 2
            return True

        return [i for i in range(len(graph)) if is_safe(i)]