802. Find Eventual Safe States - Explanation

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

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

        res = []
        for node in range(n):
            if dfs(node):
                res.append(node)
        return res

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        outdegree = [0] * n
        parents = [[] for _ in range(n)]
        queue = deque()

        for node in range(n):
            outdegree[node] = len(graph[node])
            if outdegree[node] == 0:
                queue.append(node)
            for nei in graph[node]:
                parents[nei].append(node)

        while queue:
            node = queue.popleft()
            for parent in parents[node]:
                outdegree[parent] -= 1
                if outdegree[parent] == 0:
                    queue.append(parent)

        res = []
        for node in range(n):
            if outdegree[node] <= 0:
                res.append(node)
        return res