802. Find Eventual Safe States

link

Go from the last node(terminal node) and trackback from terminal node.

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

        n = len(graph)
        M = defaultdict(list)

        outdeg = [0] * n
    

        for i, ll in enumerate(graph):
            for j in ll:
                M[j].append(i)
                outdeg[i] += 1

        
        dq = deque([i for i in range(n) if outdeg[i] == 0])

        res = []


        while dq:
            
            lens = len(dq)

            for _ in range(lens):

                idx = dq.popleft()

                res.append(idx)


                for j in M[idx]:
                    outdeg[j] -= 1
                    if outdeg[j] == 0:
                        dq.append(j)

        res.sort()

        return res