Find Eventual Safe States

Problem Id: 802 Difficulty: Medium


Intuition

Solution


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)

        self.visited = [False] * n
        self.safe = [False] * n
        self.graph = graph

        for node in range(n):
            self.dfs(node)

        return [key for key in range(n) if self.safe[key]]

    def dfs(self, node):
        if self.visited[node]:
            return self.safe[node]

        self.visited[node] = True
        if not self.graph[node]:
            self.safe[node] = True
            return True

        self.safe[node] = all([self.dfs(n) for n in self.graph[node]])
        return self.safe[node]