Find Eventual Safe States Python Solution

lcpy gen -n 802   # by problem number
lcpy gen -s find_eventual_safe_states   # by problem name

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

from collections import deque


class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def eventual_safe_nodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        # Trim nodes in reverse topological order: a node is safe once all
        # its outgoing edges point at confirmed safe nodes
        out_degree = [len(edges) for edges in graph]
        reverse: list[list[int]] = [[] for _ in range(n)]
        for u, edges in enumerate(graph):
            for v in edges:
                reverse[v].append(u)

        queue = deque(i for i in range(n) if out_degree[i] == 0)
        safe = [False] * n
        while queue:
            v = queue.popleft()
            safe[v] = True
            for u in reverse[v]:
                out_degree[u] -= 1
                if out_degree[u] == 0:
                    queue.append(u)
        return [i for i in range(n) if safe[i]]