In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.
Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.
Which nodes are eventually safe?  Return them as an array in sorted order.
The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph.  The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.
Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.



Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        \"\"\"
        Just move along unvisited (-1) nodes and remark them as 0 on the queue while visiting others on the path and finish them as 1. If you meet them again on the queue while visiting (being 0) it means you completed a cycle, in other words it is not safe and return back without adding.
        \"\"\"
        visited, result = [-1] * len(graph), []
        
        def explore(i):
            visited[i] = 0
            for v in graph[i]:
                if visited[v] == 0 or (visited[v]==-1 and explore(v)): return True
            visited[i] = 1
            result.append(i)
            return False
        
        for i in range(len(graph)):
            if visited[i] == -1: explore(i)

        return sorted(result)
            

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        N = len(graph)
        if N == 0:
            return []
        
        color = [0] * N
        in_cycle = set()
        
        def dfs(i):
            if color[i] != 0:
                return color[i] == 2
            
            color[i] = 1
            for j in graph[i]:
                if color[j] == 2:
                    continue
                elif color[j] == 1 or (dfs(j) == False):
                    return False
            color[i] = 2
            return True
        
        ret = []
        for i in range(N):
            if dfs(i):
                ret.append(i)
        return ret
        


class Solution:
    def dfs(self, node, v, g):
        if v[node]==2:
            return False
        if v[node]==1:
            return True
        if len(g[node])==0:
            v[node]=2
            return False
        v[node]=1
        for i in g[node]:
            if self.dfs(i, v, g):
                return True
        v[node]=2
        return False
    
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        if len(graph)==0:
            return []
        g = {}
        v = [0]*len(graph)
        ans = set()
        
        for i in range(len(graph)):
            if not self.dfs(i, v, graph):
                ans.add(i)
        ans = list(ans)
        ans.sort()
        return ans

from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph):
        state = defaultdict(lambda: 'unknown')
        
        def dfs(node):
            if state[node] != 'unknown':
                return state[node] == 'safe'
            state[node] = 'visiting'
            for nei in graph[node]:
                if state[nei] == 'visiting' or not dfs(nei):
                    return False
            state[node] = 'safe'
            return True
        N = len(graph)
        return [node for node in range(N) if dfs(node)]

import collections
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        Terminal = []
        dict_raw = dict()
        dict_idx = collections.defaultdict(list)
        for i, ele in enumerate(graph):
            dict_raw[i] = set(ele)
            if ele==[]: # Terminal
                Terminal.append(i)
            else:
                for idx in ele:
                    dict_idx[idx].append(i) # dict_idx[idx]: what nodes going into node idx
        # Then start from Terminal and do backsearch
        stack = Terminal
        safe = set(Terminal)
        
        while stack:
            node = stack.pop()
            for ele_1 in dict_idx[node]:
                if dict_raw[ele_1].issubset(safe) and ele_1 not in safe: # the 1-step previous node will go to all safe nodes, thus safe
                    safe.add(ele_1)
                    stack.append(ele_1)
        res = list(safe)
        return sorted(res)
                
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(snode):
            if mem[snode] == -1:
                return True
            elif mem[snode] == 1:
                return False

            mem[snode] = -1
            for e in graph[snode]:
                res = cycle(e)
                if res:
                    return True
            mem[snode] = 1
            return False

        n = len(graph)
        ret = []
        mem = [0] * n
        for i in range(n):
            if not cycle(i):
                ret.append(i)
        return ret


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # first find all the nodes that does not have out degree
        if not graph: return None
        n = len(graph)
        out_degree, rgraph = collections.Counter(), collections.defaultdict(set)
        for node, neighbors in enumerate(graph): 
            for nei in neighbors: 
                out_degree[node] += 1
                rgraph[nei].add(node)
                
        q = collections.deque([x for x in range(n) if out_degree[x] == 0])
        ans = []
        while q: 
            node = q.popleft()
            ans.append(node)
            for nei in rgraph[node]: 
                if out_degree[nei] == 0: 
                    continue
                out_degree[nei] -= 1
                if out_degree[nei] == 0: 
                    q.append(nei)
        ans.sort()
        return ans
            
        
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        if not graph:
            return []
        n = len(graph)
        adj = collections.defaultdict(set)
        for i in range(n):
            for j in graph[i]:
                adj[j].add(i)
        res = [i for i in range(n) if not graph[i]]
        outdegree = [len(graph[i]) for i in range(n)]
        Q = collections.deque(res)
        while Q:
            cur = Q.popleft()
            for i in adj[cur]:
                outdegree[i] -= 1
                if outdegree[i] == 0:
                    res.append(i)
                    Q.append(i)
        return sorted(res)
        


class Solution:
  def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    n = len(graph)
    state = [-1] * n # -1 = unvisited, 0 = involved in directed cycle, 1 = eventually safe
    
    def dfs(node):
      state[node] = 0 # may be involved in a cycle
      for adj in graph[node]:
        if state[adj] == 0 or (state[adj] == -1 and dfs(adj)):
          return True
      state[node] = 1
    
    for i in range(n):
      if state[i] == -1:
        dfs(i)
    
    return [i for i in range(n) if state[i] == 1]
    


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        outdegree = collections.defaultdict(int)
        dic = collections.defaultdict(list)
        queue = collections.deque()
        visited, res = set(), []
        for i in range(len(graph)):
            outdegree[i] += len(graph[i])
            if not graph[i]: 
                queue.append(i)
                visited.add(i)
            for node in graph[i]:
                dic[node].append(i)
        
        while queue:
            node = queue.popleft()
            res.append(node)
            for nbr in dic[node]:
                outdegree[nbr] -= 1
                if nbr not in visited and outdegree[nbr] == 0:
                    queue.append(nbr)
                    visited.add(nbr)

        return(sorted(res))
        

            
                    



class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
#         g = collections.defaultdict(list)
#         N = len(graph)
        
#         for i, end in enumerate(graph):
#             for x in end:
#                 g[i].append(x)
            
#         def dfs(node, cycle):
#             if(not g[node]):
#                 return True
            
#             c = False
#             for nei in g[node]:
#                 if(nei not in cycle):
#                     cycle.add(nei)
#                     if(not dfs(nei, cycle)):
#                         c = True
#                         break
#                     cycle.remove(nei)
#                 else:
#                     c = True
#                     break
#             if(not c):
#                 return True
#             else:
#                 return False
    
#         res = []
#         for i in range(N):
#             cycle = set()
#             cycle.add(i)
#             if(dfs(i, cycle)):
#                 res.append(i)
#         return res

#         W, G, B = 0, 1, 2
#         color = collections.defaultdict(int)
        
#         def dfs(node):
#             if(color[node] != W):
#                 return color[node] == B
            
#             color[node] = G
#             for nei in graph[node]:
#                 if(color[nei] == B):
#                     continue
#                 if(color[nei] == G or not dfs(nei)):
#                     return False
#             color[node] = B
#             return True
        
#         res = []
#         for i in range(len(graph)):
#             if(dfs(i)):
#                 res.append(i)
#         return res

        N = len(graph)
    
        # graph = map(set, graph)
        re = [set() for _ in range(N)]
        q = collections.deque([])
        
        for i, v in enumerate(graph):
            if(not v):
                q.append(i)
            for j in v:
                re[j].add(i)
        
        res = []
        while(q):
            temp = q.popleft()
            res.append(temp)
            for renei in re[temp]:
                graph[renei].remove(temp)
                if(len(graph[renei]) == 0):
                    q.append(renei)
        
        return sorted(res)


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # first find all the nodes that does not have out degree
        if not graph: return None
        n = len(graph)
        out_degree, rgraph = collections.Counter(), collections.defaultdict(set)
        for node, neighbors in enumerate(graph): 
            for nei in neighbors: 
                out_degree[node] += 1
                rgraph[nei].add(node)
                
        q = collections.deque([x for x in range(n) if out_degree[x] == 0])
        ans = []
        while q: 
            node = q.popleft()
            ans.append(node)
            for nei in rgraph[node]: 
                if out_degree[nei] != 0: 
                    out_degree[nei] -= 1
                    if out_degree[nei] == 0: 
                        q.append(nei)
        ans.sort()
        return ans
            
        
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        ans = []
        if len(graph) == 0:
            return ans
        status = [0 for _ in range(len(graph))]
        for i in range(len(graph)):
            if status[i] == 0:
                self.dfs(i, graph, status, ans)
        ans.sort();
        return ans
                
    
    def dfs(self, i, graph, status, ans):
        status[i] = 1
        for neighbor in graph[i]:
            if status[neighbor] == 1:
                return False
            if status[neighbor] == 0 and not self.dfs(neighbor, graph, status, ans):
                return False
        
        status[i] = 2
        ans.append(i)
        return True

from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        g = defaultdict(list)
        for i in range(len(graph)):
            g[i] = graph[i]
            
        array = [False]*len(graph)
        visited = [False]*len(graph)
        
        for i in range(len(graph)):
            if visited[i]==False:
                self.dfs(i,graph,visited,array)
                
        ans = []
        for i in range(len(array)):
            if array[i]==True:
                ans.append(i)
        return ans
        
        
    def dfs(self,node,graph,visited,array):
        
        visited[node] = True
        if len(graph[node])==0:
            array[node]=True
        
        else:
            b = True
            for ver in graph[node]:
                if visited[ver] ==False:
                    self.dfs(ver,graph,visited,array)
                b = b&array[ver]
            array[node] = b
            


from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph):
        state = defaultdict(int)
        
        def dfs(node):
            if state[node]:
                return state[node] == 2
            state[node] = 1
            for nei in graph[node]:
                if state[nei] == 1 or not dfs(nei):
                    return False
            state[node] = 2
            return True
        N = len(graph)
        return [node for node in range(N) if dfs(node)]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        visited = [False for i in range(len(graph))]
        recStack = [False for i in range(len(graph))]
        def dfs(node):
            visited[node] = True
            recStack[node] = True
            for nbor in graph[node]:
                if not visited[nbor]:
                    if dfs(nbor): 
                        return True
                elif recStack[nbor]: 
                    return True
            
            recStack[node] = False
            return False
        
        res = []
        for vert in range(len(graph)):
            if not dfs(vert):
                res.append(vert)
        res.sort()
        return res

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        adj = {}
        for i in range(n):
            adj[i] = set(graph[i])
        
        safe = set() 
        for i in range(n):
            if not adj[i]:
                safe.add(i)
        
        prev_size = len(safe)
        while True:
            for i in range(n):
                if i in safe:
                    continue
                for x in adj[i]:
                    if x not in safe:
                        break
                else:
                    safe.add(i)
            if len(safe) == prev_size:
                break
            else:
                prev_size = len(safe)
              
        out = []
        for i in range(n):
            if i in safe:
                out.append(i)
        return out

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        nodes = set()
        for i in range(len(graph)):
            if len(graph[i]) == 0:
                nodes.add(i)
        
        stop = False
        while not stop:
            tmp = set()
            for i in range(len(graph)):
                if i not in nodes:
                    add = True
                    for dest in graph[i]:
                        if dest not in nodes:
                            add = False
                            break
                    if add:
                        tmp.add(i)
            if len(tmp) == 0:
                stop = True
            nodes = nodes.union(tmp)
            # print(nodes)
            
        return sorted(nodes)
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
#         g = collections.defaultdict(list)
#         N = len(graph)
        
#         for i, end in enumerate(graph):
#             for x in end:
#                 g[i].append(x)
            
#         def dfs(node, cycle):
#             if(not g[node]):
#                 return True
            
#             c = False
#             for nei in g[node]:
#                 if(nei not in cycle):
#                     cycle.add(nei)
#                     if(not dfs(nei, cycle)):
#                         c = True
#                         break
#                     cycle.remove(nei)
#                 else:
#                     c = True
#                     break
#             if(not c):
#                 return True
#             else:
#                 return False
    
#         res = []
#         for i in range(N):
#             cycle = set()
#             cycle.add(i)
#             if(dfs(i, cycle)):
#                 res.append(i)
#         return res

        W, G, B = 0, 1, 2
        color = collections.defaultdict(int)
        
        def dfs(node):
            if(color[node] != W):
                return color[node] == B
            
            color[node] = G
            for nei in graph[node]:
                if(color[nei] == B):
                    continue
                if(color[nei] == G or not dfs(nei)):
                    return False
            color[node] = B
            return True
        
        res = []
        for i in range(len(graph)):
            if(dfs(i)):
                res.append(i)
        return res

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # Start at 10:19 PM
        # Need to do DFS, reduce computation if already visited the node
        visited = set()
        
        states = [None]*len(graph)
        
        def verify(i):
            if states[i] is not None:
                return states[i]
            
            # Cyclical relation detected
            if i in visited:
                return False
            visited.add(i)
            
            for j in graph[i]:
                stable = verify(j)
                
                if j in visited:
                    visited.remove(j)
                
                states[j] = stable
                
                if not stable:
                    return False
            return True

        verified_unstable = set()
        
        for i in range(len(graph)):
            if states[i] is not None:
                continue
            states[i] = verify(i)
        
        return [i for i, val in enumerate(states) if val == True]
                


#Cycle detection alg: s f pointers are only for lists and linkedlists. WGB DFS is for graph.
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        color = [0]*(len(graph)) #0 white, 1 grey, 2 black
        
        #True: black or safe    False: grey or unsafe
        def df(v):
            if color[v]==2:
                return True
            if color[v]==1:
                return False 
            
            color[v] = 1 #set it to grey while traversing
            for v2 in graph[v]:
                if color[v2]==1 or color[v2]==0 and not df(v2):
                    return False       
            color[v] = 2 #set it to black after traversing if safe
            
            return True
        
        safe = []
        for v in range(len(graph)):
            if df(v):
                safe.append(v)
        
        return safe
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        g=defaultdict(list)
        result=[]
        outDegre=[0]*len(graph)
        for i in range(len(graph)):
            outDegre[i]=len(graph[i])
            if not outDegre[i]:
                result.append(i)
            for j in graph[i]:
             g[j].append(i)
        print(outDegre)
        for nodes in result:
            for nei in g[nodes]:
                outDegre[nei]=outDegre[nei] -1 
                if outDegre[nei]==0:
                    result.append(nei)
        print(g)
        print(outDegre)
        return sorted(result)


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        outdegree = collections.defaultdict(int)
        dic = collections.defaultdict(list)
        queue = collections.deque()
        visited, res = set(), []
        for i in range(len(graph)):
            outdegree[i] += len(graph[i])
            if not graph[i]: 
                queue.append(i)
                visited.add(i)
            for node in graph[i]:
                dic[node].append(i)
                
        # print(indegree)
        # print(outdegree)
        # print(dic)
        # print(queue)
        # print('*********')
        
        while queue:
            node = queue.popleft()
            res.append(node)
            for nbr in dic[node]:
                outdegree[nbr] -= 1
                if nbr not in visited and outdegree[nbr] == 0:
                    queue.append(nbr)
                    visited.add(nbr)
            # print(queue)
        return(sorted(res))
        

            
                    



class Solution(object):
    def eventualSafeNodes(self, graph):
        WHITE, GRAY, BLACK = 0, 1, 2
        color = collections.defaultdict(int)

        def dfs(node):
            if color[node] != WHITE:
                return color[node] == BLACK

            color[node] = GRAY
            for nei in graph[node]:
                if color[nei] == BLACK:
                    continue
                if color[nei] == GRAY or not dfs(nei):
                    return False
            color[node] = BLACK
            return True

        return filter(dfs, range(len(graph)))

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        def dfs(graph, node):
            if not graph[node]:
                return True
            if node not in self.dp:
                self.dp[node] = -1
                res = True
                for nex in graph[node]:
                    res = res and dfs(graph, nex)
                self.dp[node] = res
            else:
                if self.dp[node] == -1:
                    return False
            return self.dp[node]
        
        self.dp = {}
        res = []
        for i in range(len(graph)):
            if dfs(graph, i):
                res.append(i)
        return res


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        visited = {}
        departures = [-1] * len(graph)
        res = []
        def _dfs(node):
            visited[node] = 1
            neighbors = graph[node]
        
            for neighbor in neighbors:
                if neighbor not in visited:
                    if _dfs(neighbor):
                        return True 
                else:
                    if departures[neighbor] == -1:
                        return True
                    
            departures[node] = 1
            return False
        
        
        for i in range(0, len(graph)):
            if not _dfs(i):
                res.append(i)
        return res

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        adj = {}
        for i in range(n):
            adj[i] = set(graph[i])
        
        safe = set() 
        for i in range(n):
            if not adj[i]:
                safe.add(i)
        
        prev_size = len(safe)
        while True:
            for i in range(n):
                if i in safe:
                    continue
                for x in adj[i]:
                    if x not in safe:
                        break
                else:
                    safe.add(i)
            if len(safe) == prev_size:
                break
            else:
                prev_size = len(safe)
              
        
        out = list(safe)
        out.sort()
        return out
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        res = set()
        for i in range(len(graph)):
            visited = set([i])
            self.dfs(graph, i, visited, res)
        
        return sorted(list(res))
    
    # dfs is to check if there's a cycle starting from this point
    def dfs(self, graph, i, visited, res):
        for j in graph[i]:
            if j in visited:
                return False
            # This step is not necessary for the correctness of the result, but saves time
            if j in res:
                continue
            visited.add(j)
            # Now we go on to the next step and see if there's a cycle
            if not self.dfs(graph, j, visited, res):
                return False
            visited.remove(j)
        
        res.add(i)
        return True
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        res = set()
        for i in range(len(graph)):
            visited = set([i])
            self.dfs(graph, i, visited, res)
        
        return sorted(list(res))
    
    # dfs is to check if there's a cycle starting from this point
    def dfs(self, graph, i, visited, res):
        for j in graph[i]:
            if j in visited:
                return False
            if j in res:
                continue
            visited.add(j)
            # Now we go on to the next step and see if there's a cycle
            if not self.dfs(graph, j, visited, res):
                return False
            visited.remove(j)
        
        res.add(i)
        return True
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        res = set()
        for i in range(len(graph)):
            visited = set()
            self.dfs(graph, i, visited, res)
        
        return sorted(list(res))
    
    # dfs is to check if there's a cycle starting from this point
    def dfs(self, graph, i, visited, res):
        visited.add(i)
        for j in graph[i]:
            if j in visited:
                return False
            if j in res:
                continue
            if not self.dfs(graph, j, visited, res):
                return False
        visited.remove(i)
        res.add(i)
        return True

            


from typing import Dict, List, Set


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        result = []
        graph_map: Dict[int, Set[int]] = {}
        reverse_graph_map: Dict[int, Set[int]] = {}
        for i, edges in enumerate(graph):
            graph_map[i] = set(edges)
            for n in edges:
                reverse_graph_map.setdefault(n, set())
                reverse_graph_map[n].add(i)

        while True:
            to_remove = set()
            for i, edges in list(graph_map.items()):
                if len(edges) == 0:
                    to_remove.add(i)
            if len(to_remove) == 0:
                break

            result.extend(to_remove)

            for i in to_remove:
                del graph_map[i]
                for n in reverse_graph_map.get(i, set()):
                    graph_map[n].remove(i)

        return sorted(result)


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        flags = [0] * len(graph)
        
        def dfs(node, visited):
            visited.add(node)
            for neighbor in graph[node]:
                if flags[neighbor] == 1:
                    continue
                if flags[neighbor] == -1:
                    return False
                if neighbor in visited or not dfs(neighbor, visited.copy()):
                    flags[neighbor] = -1
                    return False
            flags[node] = 1
            return True
        
        visited = set()
        for i in range(len(graph)):
            if not flags[i]:
                dfs(i, visited)
        return [i for i, flag in enumerate(flags) if flag==1]

class Solution:
    
    def isCycle(self, src, graph: List[List[int]], visited):
        
        
        
        WHITE, GRAY, BLACK = 0, 1, 2
        
        if visited[src] != WHITE:
            return visited[src] == GRAY 
        
        stack = []
    
        stack.append((src,1))
        stack.append((src,0))
        
        while stack:
            # print(stack)
            # print(visitedNodes)
            current = stack.pop()
            if current[1] == 1:
                visited[current[0]] = BLACK
                continue
            current = current[0]
            visited[current] = GRAY
            
            
            for e in graph[current]:
                
                # if not visited[e]:
                if visited[e] == GRAY:
                    # print('here', e)
                    return True
                    
                if visited[e] == WHITE:
                    stack.append((e, 1))  
                    stack.append((e, 0))  
            
        return False
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        eventualSafe = []
        visited = [0] * len(graph)
        for i in range(len(graph)):
            # print('Node :', i)
            if not self.isCycle(i, graph, visited):
                # print('Found you')
                eventualSafe.append(i)
        
        
        return eventualSafe
    
    
            
            
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # no out/ all out are safe state
        degree = [len(row) for row in graph]
        children = collections.defaultdict(list)
        
        for i,row in enumerate(graph):
            for j in row:
                children[j].append(i)
                
                
        seen = set()
        bfs = [i for i in range(len(degree)) if degree[i]==0]
        for val in bfs:
            if val in seen:
                continue
            seen.add(val)
            for child in children[val]:
                degree[child]-=1
                if not degree[child]:
                    bfs.append(child)
        return sorted(list(seen))

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def explore(i):
            visited[i] = 0
            for v in graph[i]:
                if visited[v] == 0 or (visited[v] == -1 and explore(v)): return True
            visited[i] = 1
            res.append(i)
            return False
        visited, res = [-1] * len(graph), []
        for i in range(len(graph)):
            if visited[i] == -1: explore(i)
        return sorted(res)
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        safe_nodes = set()
        
        for i, node in enumerate(graph):
            if len(node) == 0:
                safe_nodes.add(i)
        
        while True:
            starting_len = len(safe_nodes)
            for i, node in enumerate(graph):
                all_safe = True
                for j in node:
                    if j not in safe_nodes:
                        all_safe = False
                        break
                if all_safe:
                    safe_nodes.add(i)
            if starting_len == len(safe_nodes):
                break
        
        return sorted(list(safe_nodes))

class Solution:
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        out_degree = collections.defaultdict(int)
        inward_nodes = collections.defaultdict(list)   # recording the nodes going into the 'key' node
        
        for src in range(len(graph)):
            for child in graph[src]:
                inward_nodes[child].append(src)
                out_degree[src] += 1
        
        q = collections.deque()
        for i in range(len(graph)):
            if not i in out_degree:
                q.append(i)
        
        result = []
        while q:
            top = q.popleft()
            result.append(top)
            for parent in inward_nodes[top]:
                out_degree[parent] -= 1
                if out_degree[parent] == 0:
                    q.append(parent)
        return sorted(result)

#Cycle detection alg: s f pointers are only for lists and linkedlists. WGB DFS is for graph.
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        color = [0]*(len(graph)) #0 white, 1 grey, 2 black
        
        def df(v):
            if color[v]==2:
                return True
            
            color[v] = 1 #set it to grey while traversing
            for v2 in graph[v]:
                if color[v2]==1 or color[v2]==0 and not df(v2):
                    return False       
            color[v] = 2 #set it to black after traversing if safe
            
            return True
        
        safe = []
        for v in range(len(graph)):
            if df(v):
                safe.append(v)
        
        return safe
        


#Cycle detection alg: s f pointers are only for lists and linkedlists. WGB DFS is for graph.
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        color = [0]*(len(graph)) #0 white, 1 grey, 2 black
        
        def df(v):
            if color[v]==2:
                return True
            if color[v]==1: #Grey nodes will stay grey if cycle found. THis is for when doing WGB DFS for every node.
                return False 
            
            color[v] = 1 #set it to grey while traversing
            for v2 in graph[v]:
                if color[v2]==1 or color[v2]==0 and not df(v2):
                    return False       
            color[v] = 2 #set it to black after traversing if safe
            
            return True
        
        safe = []
        for v in range(len(graph)):
            if df(v):
                safe.append(v)
        
        return safe
        


class Solution:\r
    def eventualSafeNodes(self, graph):\r
        def dfs(i):\r
            # return false if cyclic\r
            colors[i] = 1  # checking, set color to \"gray\"\r
            # scan all the neighbor\r
            for v in graph[i]:\r
                if colors[v] == 1:\r
                    # cycle detected\r
                    return False\r
                if colors[v] == 0 and dfs(v) == False:\r
                    return False\r
            res.append(i)\r
            colors[i] = 2\r
            return True\r
\r
        colors = [0] * len(graph)\r
        res = []\r
\r
        for i, neighbors in enumerate(graph):\r
            if not colors[i]:\r
                dfs(i)\r
\r
        return sorted(res)\r
\r


class Solution:
    data = {}
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        result = []
        # print(result, self.data)
        self.data = {}
        for i in range(len(graph)):
            if i in self.data:
                if self.data[i]:
                    result.append(i)
            else:
                res = self.check(graph, i, [])
                if res == True:
                    result.append(i)
                    self.data[i] = True
                    
        return result
        
    def check(self, graph, curr, path):
        if curr in path:
            self.data[curr] = False
            for p in path:
                self.data[p] = False
            return False

        if len(graph[curr]) == 0:
            self.data[curr] = True
            return True
        
        result = True
        for n in graph[curr]:
            if n == curr:
                self.data[n] = False
                return False
            
            if n in self.data:
                result = result and self.data[n]
            else:
                res = self.check(graph, n, path + [curr])
                result = result and res
            if result == False:
                return False

        if result == True:
            self.data[curr] = True

        return True


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # list of node out degrees
        n = len(graph)
        out_degrees = [0] * n
        # list of nodes that point to this node
        node_lsts = collections.defaultdict(list)
        queue = []
        # instantiate empty lists of nodes to point, outdegrees
        for i in range(len(graph)):
            out_degrees[i] = len(graph[i])
            if out_degrees[i] == 0: queue.append(i)
            for j in graph[i]: node_lsts[j].append(i)
        # loop through deleting stuff from queue
        for term_node in queue:
            for n in node_lsts[term_node]:
                out_degrees[n] -= 1
                if out_degrees[n] == 0:
                    queue.append(n)
        return sorted(queue)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        state = ['UNPROCESSED'] * n
        def isAcyclic(node):
            if state[node] == 'PROCESSING':
                return False
            elif state[node] == 'PROCESSED':
                return True
            else:
                state[node] = 'PROCESSING'
                if any(not isAcyclic(nei) for nei in graph[node]):
                    return False
                state[node] = 'PROCESSED'
                return True
        return list(filter(isAcyclic, list(range(n))))

\"\"\"
0 - unvisited
1 - currently visiting in the current DFS traversal
2 - already visited
\"\"\"
WHITE = 0
GRAY = 1
BLACK = 2

from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        if not g:
            return []
        
        res = []
        g = defaultdict(list)
        n = len(graph)
        currRecurStack = [WHITE] * n
        visited = set()
        cycleExists = False
        
        for i in range(n):
            for vertex in graph[i]:
                g[i].append(vertex)
        
        
        for i in range(n):
            if i not in visited:
                cycleExists = dfsDetectCycle(g, visited, currRecurStack, i)
                if not cycleExists:
                    res.append(i)
        
        return res
                
            
    

def dfsDetectCycle(g, visited, currRecurStack, i):
    visited.add(i)
    currRecurStack[i] = GRAY
    
    neighbors = g[i]
    for nh in neighbors:
        if (nh not in visited and dfs(g, visited, currRecurStack, nh)): return True
        if (currRecurStack[nh] == GRAY): return True
    
    currRecurStack[i] = BLACK
    return False
















































from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # visited = set()
        n = len(graph)
        # recur = [False] * n
        color = [0] * n
        g = defaultdict(list)
        ans = []
        
        for i in range(n):
            for nh in graph[i]:
                g[i].append(nh)
        
        for i in range(n):
            if not dfsCycle(g, i, color):
                ans.append(i)
        
        return ans

# alternate version with same logic
\"\"\"    
def dfsCycle2(g, node, recur, visited):
    visited.add(node)
    recur[node] = True
    
    for nh in g[node]:
        if (nh not in visited and dfsCycle2(g, nh, recur, visited)): return True
        if (recur[nh]): return True
    
    recur[node] = False
    return False
\"\"\"

def dfsCycle(g, node, color):
    color[node] = 1
    neighbours = g[node]
    
    for nh in neighbours:
        if (color[nh] == 0 and dfsCycle(g, nh, color)): return True
        if (color[nh] == 1): return True
    
    color[node] = 2
    return False

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        WHITE, GRAY, BLACK = 0, 1, 2    #GRAY is part of a cycle, BLACK is safe
        color = {}
        for i in range(len(graph)):
            color[i] = WHITE
         
        # Return whether it is safe
        def dfs(node):
            if color[node] != WHITE:
                return color[node] == BLACK
            
            color[node] = GRAY
            for nei in graph[node]:
                if color[nei] == BLACK:
                    continue
                elif color[nei] == GRAY:
                    return False
                elif not dfs(nei):
                    return False
            color[node] = BLACK
            return True
        
        safe = []
        for i in range(len(graph)):
            if dfs(i):
                safe.append(i)
                
        return safe
            
            
            
            
        
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        
        def cycle(index):
            if visited[index] == 1:
                return True
            if visited[index] == 2:
                return False
            
            visited[index] = 1
            for node in graph[index]:
                if cycle(node):
                    return True
                
            visited[index] = 2
            return False
        
        
        visited = [0] * len(graph)
        
        for i in range(len(graph)):
            cycle(i)
                    
        safe = []
        for i in range(len(graph)):
            if visited[i] == 2:
                safe.append(i)
        return safe

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        def dfs(node):
            # if
            # print(\"node\",node)
            if(node in terminalnodes):
                return True
            if(node in visited):
                return False
            visited[node] = 1
            a = True
            for newnodes in graph[node]:
                a = a and dfs(newnodes)
                
            if(a==True):
                terminalnodes.add(node)
                return True
            else:
                return False
        
        
        
        
        nodes = len(graph)
        
        m = []
        # print(len(m))
        
        nonlocal terminalnodes
        terminalnodes = {i for i in range(nodes) if len(graph[i])==0}
        print(terminalnodes)
        nonlocal visited
        visited = {}
        for i in range(len(graph)):
            visited = {}
            a = dfs(i)
            if(a==True):
                terminalnodes.add(i)
        if(len(terminalnodes)==0):
            return []
        
        t = list(terminalnodes)
        t.sort()
        return t   


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        notSafe = set()
        safe = set()
        def isSafe(node,visited):
            if node in notSafe: return False
            if not graph[node]: return True
            if node in safe: return True
            #print(node)
            visited.add(node)
            for child in graph[node]:
                if child in visited: 
                    notSafe.add(child)
                    notSafe.add(node)
                    return False
                if not isSafe(child,set(visited)): 
                    notSafe.add(child)
                    notSafe.add(node)
                    return False
            safe.add(node) 
            return True
        out = []
        for i in range(len(graph)):
            if  isSafe(i,set()): out+=i,
        return out        

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # table = collections.defaultdict(list)
        # for i in range(len(graph)):
        #     table[i] = graph[i]
        
        #寻找从一个点出发，是否有环
        def dfs(i):
            if color[i] == 1:
                return False
            elif color[i] == 2:
                #下面不需要ans.append(i),因为在color从1到2的时候就已经被加进了ans！！
                # ans.append(i)
                return True
            elif color[i] == 0:
                color[i] = 1
                for j in graph[i]:
                    #不能直接dfs(j),因为这样dfs(j)有可能是false，但是却没有退出，导致后面还会执行
                    # color[i] = 2 ans.append(i) return True
                    # dfs(j)
                    #下面是要对false判断，如果是false直接退出
                    if not dfs(j):
                        return False
                color[i] = 2
                ans.append(i)
                return True
                
                
        ans = []
        color = [0] * len(graph)
        for i in range(len(graph)):
            if color[i] == 0:
                dfs(i)
        return sorted(ans)
            
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(snode):
            if mem[snode] == -1:
                return True
            elif mem[snode] == 1:
                return False

            seen_path.add(snode)
            for e in graph[snode]:
                if e in seen_path:
                    for n in seen_path:
                        mem[n] = -1
                    return True
                if e not in seen:
                    seen.add(e)
                    res = cycle(e)
                    if res:
                        return res
            mem[snode] = 1
            seen_path.discard(snode)
            return False

        ret = []
        seen = set()
        seen_path = set()
        mem = [0] * len(graph)
        for i in range(len(graph)):
            seen_path.clear()
            seen.clear()
            if not cycle(i):
                ret.append(i)
        return ret



class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        terminal = []
        n = len(graph)
        visited = [-1]*n
        
                
        def dfs(i):
            visited[i] = 0 # i is visiting
            for t in graph[i]:
                if visited[t] == 0 or (visited[t]==-1 and not dfs(t)):
                    return False
            visited[i] = 1 # i visited already
            terminal.append(i)
            return True
                
        for i in range(n):
            if visited[i] == -1:
                dfs(i)
                
        return sorted(terminal)

class Solution:
    def eventualSafeNodes(self, graph):
        \"\"\"
        :type graph: List[List[int]]
        :rtype: List[int]
        \"\"\"
        n = len(graph)
        res = set([i for i in range(n) if graph[i] == []])
        left = set(range(n)) - res
        while True:
            new_res = set(res)
            new_left = set(left)
            for i in left:
                if set(graph[i]).issubset(res):
                    new_res.add(i)
                    new_left.remove(i)
            if new_res == res:
                return sorted(list(res))
            else:
                res = new_res
                left = new_left

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        graph = list(map(set, graph))
        rgraph = defaultdict(set)
        q = deque()
        
        for i, nn in enumerate(graph):
            if not nn:
                q.append(i)
            for j in nn:
                rgraph[j].add(i)
        res = []
        while q:
            j = q.popleft()
            res.append(j)
            for i in rgraph[j]:
                graph[i].remove(j)
                if not graph[i]:
                    q.append(i)
        res.sort()
        return res
    
#     def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
#         self.nope = set()
#         res = []
#         for i in range(len(graph)):
#             if i in self.nope:
#                 continue
#             if not self.has_cycle(graph, i, i, set()):
#                 res.append(i)
#         return res
        
        
#     def has_cycle(self, graph, i, root, seen):
#         # print('here', i, root, seen)
#         if i == root and root in seen:
#             self.nope.add(i)
#             return True
#         if i in seen:
#             self.nope.add(i)
#             return True
        
#         res = False
#         seen.add(i)
#         for nei in graph[i]:
#             res |= self.has_cycle(graph, nei, root, seen)
#         seen.remove(i)
#         return res


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def check_safe(graph, st, seen, cur):
            if st[cur] != 0:
                return st[cur]
            if len(graph[cur]) == 0:
                return 1
            if cur in seen:
                return -1
            seen.add(cur)
            for ne in graph[cur]:
                rtv = check_safe(graph, st, seen, ne)
                if rtv == -1:
                    st[cur] = -1
                    return -1
            seen.discard(cur)
            st[cur] = 1
            return 1
        
        N = len(graph)
        st= [0] * N #   -1不安全、0不确定、1安全

        for i in range(N):
            if st[i] != 0:
                continue
            seen = set()
            st[i] = check_safe(graph, st, seen, i)
        # print(st)
        rtv = []
        for i,s in enumerate(st):
            if s == 1:
                rtv.append(i)
        return rtv


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        out_degree = [0] * n
        in_nodes = collections.defaultdict(list) 
        queue = []
        for i in range(n):
            out_degree[i] = len(graph[i])
            if out_degree[i] == 0: queue.append(i)
            for j in graph[i]: in_nodes[j].append(i)  
        for term_node in queue:
            for in_node in in_nodes[term_node]:
                out_degree[in_node] -= 1
                if out_degree[in_node] == 0: queue.append(in_node)
        return sorted(queue)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        WHITE, GRAY, BLACK = 0, 1, 2    #GRAY is part of a cycle, BLACK is safe
        color = {}
        for i in range(len(graph)):
            color[i] = WHITE
         
        # Return whether it is safe
        def dfs(node):
            if color[node] != WHITE:
                return color[node] == BLACK
            
            color[node] = GRAY
            for nei in graph[node]:
                if color[nei] == GRAY:
                    return False
                elif not dfs(nei):
                    return False
            color[node] = BLACK
            return True
                
        return list(filter(dfs, list(range(len(graph)))))
            
            
            
            
        
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        
        res = []
        degree = [0]*n
        reverseGraph = collections.defaultdict(list)
        q = collections.deque()
           
        for i in range(n):
            if len(graph[i])==0:
                q.append(i)
            for nextNode in graph[i]:
                reverseGraph[nextNode].append(i)
                degree[i]+=1
        
        while q:
            index = q.popleft()
            res.append(index)
            for nextNode in reverseGraph[index]:
                degree[nextNode]-=1
                if degree[nextNode]==0:
                    q.append(nextNode)
        
        return sorted(res)
            
                
                


#[] Graph(Reversed-Topology, outdegree)
#1) node A has no child nodes => A must be stable
#2) All childs of node A are stable => A must be stable
#Solution: Traverse all nodes in reversed topological order (remove nodes with out-degree==0 first)
from collections import defaultdict, deque
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        revadj, outdegree = defaultdict(list), dict()
        for src, dsts in enumerate(graph):
            for dst in dsts:
                revadj[dst].append(src)
            outdegree[src] = len(dsts)
        q, res = deque([i for i, d in outdegree.items() if d == 0]), []
        while q:
            dst = q.popleft()
            res.append(dst)
            for src in revadj[dst]:
                outdegree[src] -= 1
                if outdegree[src] == 0:
                    q.append(src)
        return sorted(res)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        v = [0] * n 
        def circle(i):
            if v[i] == 2: return False
            if v[i] == 1: return True 
            v[i] = 1 
            for nei in graph[i]:
                if circle(nei): return True 
            v[i] = 2
            return False 
        
        res = []
        for i in range(n):
            if circle(i): continue
            res.append(i)
        return res


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        safe = [False for _ in range(n)]
        
        rgraph = [set([]) for _ in range(n)]
        
        queue = collections.deque([])
        
        for i in range(n):
            if not graph[i]:
                queue.append(i)
            else:
                for j in graph[i]:
                    rgraph[j].add(i)
        
        while queue:
            curr_node = queue.popleft()
            
            safe[curr_node] = True
            
            for prev in rgraph[curr_node]:
                graph[prev].remove(curr_node)
                
                if len(graph[prev]) == 0:
                    queue.append(prev)
        return [i for i, s in enumerate(safe) if s]
                
                
                
                
                


#dfs, with status: UNKNOWN, VISITING, VISITED
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        UNKNOWN, VISITING, VISITED = 0, 1, 2
        status = [UNKNOWN] * len(graph)
        def dfs(node):
            if status[node] == UNKNOWN:
                status[node] = VISITING
                if all([dfs(n) for n in graph[node]]):
                    status[node] = VISITED
                    return True
                else:
                    return False
            elif status[node] == VISITED:
                return True
            elif status[node] == VISITING:
                return False
        for n in range(len(graph)):
            if status[n] == UNKNOWN:
                dfs(n)
        return sorted([x for x, stat in enumerate(status) if stat == VISITED])

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        dic = collections.defaultdict(list)
        
        for i, e in enumerate(graph):
            for j in e:
                dic[i].append(j)
        
        memo = {}
        def dfs(node):
            if not dic[node]:
                return True
            
            if node in memo:
                return memo[node]
            
            memo[node] = False
            if all(dfs(nxt) for nxt in dic[node]):
                memo[node] = True
            
            return memo[node]
        
        res = []
        for i in range(len(graph)):
            if dfs(i):
                res.append(i)
        return res
        
        # for k, v in sorted(memo.items(), key = lambda x: x[1]):
        #     if v:
        #         res.append(v)


'''
Graph DFS brute force search
'''
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # cycle detection
        # initial state 0, processing 1, eventual state 2
        n = len(graph)
        
        states = [0 for i in range(n)]
        
        def dfs(i):
            if states[i] != 0:
                return states[i]
            
            if not graph[i]:
                states[i] = 2
                return states[i]
            
            states[i] = 1
            eventual_state = 2
            for j in graph[i]:
                if states[j] == 0:
                    state_j = dfs(j)
                else:
                    state_j = states[j]
                eventual_state = min(state_j, eventual_state)
            
            states[i] = eventual_state
            return states[i]
        
        
        output = []
        for i in range(n):
            s = dfs(i)
            if s == 2:
                output.append(i)
        
        return sorted(output)

#topology, indegree + bfs
#if the node doesn't point to other node, which means it will not get to the loop, so it is stable.
#so we could count the degree of each node, degree[i] = how many node can i get to from node_i.
#build a adj, adj[i] = who can get to node_i
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        adj = defaultdict(list)
        degree = dict()
        for i, node in enumerate(graph):
            degree[i] = len(node)
            for n in node:
                adj[n].append(i)
        bfs = deque([x for x, count in degree.items() if count == 0])
        result = []
        while bfs:
            current = bfs.popleft()
            result.append(current)
            for n in adj[current]:
                degree[n] -= 1
                if degree[n] == 0:
                    bfs.append(n)
        return sorted(result)

from collections import defaultdict

class Solution:
    def dfs(self, node, graph, eventuallySafe, visited):
        if node in eventuallySafe:
            return True
        if node in visited:
            return False
        
        # never seen before
        visited.add(node)
        adjNodes = graph[node]
        if len(adjNodes) != 0:
            isEventuallySafe = True
            for neighbour in adjNodes:
                isEventuallySafe = self.dfs(neighbour, graph, eventuallySafe, visited) and isEventuallySafe
            
            if not isEventuallySafe:
                return False

        # eventually safe, or safe
        eventuallySafe.add(node)
        return True

        
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # isSafe(n) <==> n.edges = {}
        # isEventuallySafe(n) <=> for_all e IN n.edges, isEventuallySafe(n) || isSafe(n)
        
        eventuallySafe = set()
        visited = set()
        for n in range(len(graph)):
            self.dfs(n, graph, eventuallySafe, visited)
            
        return sorted(list(eventuallySafe))
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        adj_list = defaultdict(list)
        vertices_with_no_incoming_edges = []
        stack = deque()
        indegree_graph = defaultdict(int) 
        vertices_part_of_cycle = []
        no_of_vertices = len(graph)

        for i in range(no_of_vertices):
            indegree_graph[i] = 0

        for source in range(no_of_vertices):
            for dest in graph[source]:
                adj_list[dest].append(source) 
                indegree_graph[source] += 1

        for key, val in indegree_graph.items():
            if indegree_graph[key] == 0:
                stack.append(key)
                vertices_with_no_incoming_edges.append(key)

        while stack:
            vert = stack.pop()

            if vert in adj_list:
                for v in adj_list[vert]:
                    indegree_graph[v] -= 1
                
                    if indegree_graph[v] == 0:
                        vertices_with_no_incoming_edges.append(v)
                        stack.append(v)

        return sorted(vertices_with_no_incoming_edges) 

# DFS / Topological Method
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        WHITE, GREY, BLACK = 0,1,2
        result=[]
        
        # 1) assign colors for all nodes
        color=defaultdict()
        for i in range(len(graph)):
            color[i]=WHITE
        
        # 2) dfs the nodes
        def dfs(node):
            if color[node] != WHITE:          # this node was visited, could be grey or black
                return color[node] == BLACK       # shortcut return 
            
            color[node]=GREY                    # visiting node so color it grey
            for neigh in graph[node]:           # visit all neighbors of current node
                if not dfs(neigh):
                    return False
                
            color[node]=BLACK                   # Done visiting this node so mark it Black
            return True

        # 3) check all nodes in graph
        for i in range(len(graph)):             # check each node in graph
            if not graph[i]:             # if node has no outgoing edges it must be a terminal node
                result.append(i)
            elif dfs(i):                        
                result.append(i)
        
        return result

    # Complexity: O(N+E)   N-nodes, for each node, have to explore all its edges.


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        graph_reverse = collections.defaultdict(list)
        indegree = collections.defaultdict(int)
        for i in range(len(graph)):
            if not graph[i]:
                indegree[i]
            for nei in graph[i]:
                graph_reverse[nei].append(i)
                indegree[nei]
                indegree[i] += 1
        q = collections.deque([node for node in indegree if indegree[node] == 0])
        res = []
        while q:
            node = q.popleft()
            res.append(node)
            for nei in graph_reverse[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)
        return sorted(res)


#[Runtime: 736 ms, faster than 57.43%] DFS
#O(V + E)
from collections import defaultdict
UNKNOWN, VISITING, VISITED = 0, -1, 1
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        visited = defaultdict(int)
        def dfs(cur: int) -> bool:
            \"\"\"return True if there is cycle\"\"\"
            if visited[cur] == VISITED:
                return False
            elif visited[cur] == VISITING:
                return True
            visited[cur] = VISITING
            if any(dfs(nxt) for nxt in graph[cur]):
                return True
            visited[cur] = VISITED
            return False
        return [i for i in range(len(graph)) if not dfs(i)]

#[] DFS
#O(V + E)
from collections import defaultdict
UNKNOWN, VISITING, VISITED = 0, 1, 2
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        adj, visited = defaultdict(list), defaultdict(int)
        #build graph
        for src, dsts in enumerate(graph):
            for dst in dsts:
                adj[src].append(dst)
        def dfs(cur: int) -> bool:
            \"\"\"return True if there is cycle\"\"\"
            if visited[cur] == VISITED:
                return False
            elif visited[cur] == VISITING:
                return True
            visited[cur] = VISITING
            res = any(dfs(nxt) for nxt in adj[cur])
            if not res:
                visited[cur] = VISITED
            return res
        return [i for i in range(len(graph)) if not dfs(i)]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        nodes = reduce(lambda node, e: node[e[0]].extend(e[1]) or node, enumerate(graph), defaultdict(list))
        
        visited = set() 
        s = set()
        def dfs(i):
            if i in s:
                return False
            if i in visited:
                return True
            
            s.add(i)
            if not all(map(dfs, nodes[i])):
                return False
            s.remove(i)
            visited.add(i)
            return True 
        
        return [i for i in range(len(graph)) if dfs(i)]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        deg = {}
        grev = {}
        terminals = []
        for i in range(n):
            deg[i] = len(graph[i])
            if deg[i] == 0:
                terminals.append(i)
            for j in graph[i]:
                if j not in grev:
                    grev[j] = []
                grev[j].append(i)
        for t in terminals:
            if t not in grev:
                continue
            for j in grev[t]:
                deg[j] -= 1
                if deg[j] == 0:
                    terminals.append(j)
        return sorted(terminals)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        graph_reverse = collections.defaultdict(list)
        indegree = collections.defaultdict(int)
        for i in range(len(graph)):
            if not graph[i]:
                indegree[i]
            for nei in graph[i]:
                graph_reverse[nei].append(i)
                indegree[nei]
                indegree[i] += 1
        q = collections.deque([node for node in indegree if indegree[node] == 0])
        res = [False for _ in range(len(graph))]
        while q:
            node = q.popleft()
            res[node] = True
            for nei in graph_reverse[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)
        return [i for i in range(len(res)) if res[i] == True]


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        safe = set()
        revg = defaultdict(set)
        q = deque()
        
        graph = list(map(set,graph))
        
        for u,nodes in enumerate(graph):
            if not nodes:
                q.append(u)
            for v in nodes:
                revg[v].add(u)
                
        while q:
            temp = q.popleft()
            safe.add(temp)
            for v in revg[temp]:
                graph[v].remove(temp)
                if not graph[v]:
                    q.append(v)
                    
        return sorted(safe)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        out_degree = collections.defaultdict(int)
        in_nodes = collections.defaultdict(list) 
        queue = []
        ret = []
        for i in range(n):
            out_degree[i] = len(graph[i])
            if out_degree[i]==0:
                queue.append(i)
            for j in graph[i]:
                in_nodes[j].append(i)  
        while queue:
            term_node = queue.pop(0)
            ret.append(term_node)
            for in_node in in_nodes[term_node]:
                out_degree[in_node] -= 1
                if out_degree[in_node]==0:
                    queue.append(in_node)
        return sorted(ret)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        ans = []
        
        def dfs(node):
            #print(i, \" \", arr)
            if arr[node] != -1:
                return arr[node] == 1
            arr[node] = 0
            for j in graph[node]:
                #print(j)
                if arr[j] == 1:
                    continue
                elif arr[j] == 0 or not dfs(j):
                    return False
            arr[node] = 1
            return True
        
        arr = [-1]*n
        for i in range(n):
            if len(graph[i]) == 0:
                ans.append(i)
                continue
            if dfs(i):
                ans.append(i)
        return ans    

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(snode):
            if mem[snode] < 0:
                return True
            elif mem[snode] > 0:
                return False

            mem[snode] = -1
            for e in graph[snode]:
                if cycle(e):
                    return True
            mem[snode] = 1
            return False

        n = len(graph)
        ret = []
        mem = [0] * n
        for i in range(n):
            if not cycle(i):
                ret.append(i)
        return ret


class Solution:
    def eventualSafeNodes(self, graph):
        degrees = {}
        safe, unsafe = set(), set()
        adj = {}
        for node in range(len(graph)):
            nodes = graph[node]
            degrees[node] = len(nodes)
            graph[node] = set(nodes)
            if node not in adj:
                adj[node] = set()
            for another in nodes:
                if another not in adj:
                    adj[another] = set()
                adj[another].add(node)
        queue = []
        for node in degrees:
            if degrees[node] == 0:
                queue.append(node)
        while True:
            if len(queue) == 0:
                break
            node = queue.pop()
            if degrees[node] == 0:
                safe.add(node)
                for another in adj[node]:
                    degrees[another] -= 1 
                    if degrees[another] == 0 and another not in safe:
                        queue.append(another)
            else:
                break
        safe = list(safe)
        safe.sort()
        return safe
                
                
                
                
        

                
            
                


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(snode):
            if mem[snode] == -1:
                return True
            elif mem[snode] == 1:
                return False

            mem[snode] = -1
            for e in graph[snode]:
                if cycle(e):
                    return True
            mem[snode] = 1
            return False

        n = len(graph)
        ret = []
        mem = [0] * n
        for i in range(n):
            if not cycle(i):
                ret.append(i)
        return ret


#[Runtime: 736 ms, faster than 57.43%] DFS
#O(V + E)
from collections import defaultdict
UNKNOWN, VISITING, VISITED = 0, 1, 2
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        adj, visited = defaultdict(list), defaultdict(int)
        #build graph
        for src, dsts in enumerate(graph):
            for dst in dsts:
                adj[src].append(dst)
        def dfs(cur: int) -> bool:
            \"\"\"return True if there is cycle\"\"\"
            if visited[cur] == VISITED:
                return False
            elif visited[cur] == VISITING:
                return True
            visited[cur] = VISITING
            if any(dfs(nxt) for nxt in adj[cur]):
                return True
            visited[cur] = VISITED
            return False
        return [i for i in range(len(graph)) if not dfs(i)]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        ans = []
        N = len(graph)
        out = collections.defaultdict(set)
        in_cnt = [0 for _ in range(N)]
        ready = set(range(N))
        for end in range(N):
            for start in graph[end]:
                out[start].add(end)
                in_cnt[end] += 1
                if end in ready:
                    ready.remove(end)
        
        while len(ready) > 0:
            rm = ready.pop()
            ans.append(rm)
            for nei in out[rm]:
                in_cnt[nei] -= 1
                if in_cnt[nei] == 0:
                    ready.add(nei)
        return sorted(ans)

        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        cycle = set()
        used = set()
        
        def do(cur, path=set()):
            if cur in used:
                return True
            if cur in cycle or cur in path:
                return False
            for nxt in graph[cur]:                
                if not do(nxt, path | {cur}):
                    cycle.update({cur, nxt})
                    return False
            used.add(cur)
            return True
        
        return list(filter(do, range(len(graph))))

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        new_g = {i: [] for i in range(len(graph))}
        for i, n in enumerate(graph):
            new_g[i].append(n)
        
        def dfs(n):
            if status[n] == -1:
                return False
            if status[n] == 1:
                return True
            status[n] = -1
            for adj in graph[n]:
                if not dfs(adj):
                    return False
            status[n] = 1
            return True
        status = [0 for _ in range(len(graph))]
        return filter(dfs, range(len(graph)))

# visiting, safe, unsafe
from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph):
        state = defaultdict(int)
        def dfs(node):
            if state[node] == 1:
                state[node] = 3
                return 3
            if state[node]:
                return state[node]
            state[node] = 1
            for nei in graph[node]:
                if dfs(nei) == 3:
                    state[node] = 3
                    return 3
            state[node] = 2
            return 2
        N = len(graph)
        return [node for node in range(N) if dfs(node) == 2]

from collections import defaultdict, deque
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        degree = [len(graph[i]) for i in range(len(graph))]
        edges = defaultdict(list)
        for i in range(len(graph)):
            for j in graph[i]:
                edges[j].append(i)
        
        q = deque()
        for i in range(len(graph)):
            if degree[i] == 0:
                q.append(i)
        
        res = []
        while q:
            node = q.popleft()
            res.append(node)
            for n in edges[node]:
                degree[n] -= 1
                if degree[n] == 0:
                    q.append(n)
        return sorted(res)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        perm = {i for i, e in enumerate(graph) if not e}

        rev = [[] for i in range(len(graph))]

        for i, e in enumerate(graph):
            for j in e:
                rev[j].append(i)

        last = perm.copy()
        while last:
            tmp = set()
            for n in last:
                for nei in rev[n]:
                    if nei not in perm and all(cat in perm for cat in graph[nei]):
                        tmp.add(nei)
            perm = perm.union(tmp)
            last = tmp

        return sorted(perm)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        unsafe_nodes = set()
        
        safe_nodes = set()
        
        def dfs(node, visited):
            if node in visited:
                return False
            
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor in unsafe_nodes:
                    unsafe_nodes.add(node)
                    return False
                if neighbor in safe_nodes:
                    continue
                if not dfs(neighbor, visited):
                    unsafe_nodes.add(node)
                    return False
     
            safe_nodes.add(node)
            return True
        
        safe = []
        for i in range(len(graph)):
            if dfs(i,set()):
                safe.append(i)
                
        return safe

class Solution:
    
    # Check each vertex to see if its part of a cycle
    # If it is, it is not a safe vertex.
    
    # All nodes in that cycle are not considered to be safe vertices
    
    # Nodes that have no directed edges are also considered to be safe.
    
    # A node is considered safe it all its edges are to nodes that will eventually
    # become safe. So it one edge points to a safe node, but the other edge points to a 
    # cycle, that node is stil considered unsafe.
    
    # Even union find fails algo? Yes. You can group up safe nodes with cycles
    # Union find helps you prevent cycles, but not this application.
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        # If parent node i has no incoming edges (i,j) where parent (k) of 
        # node j is also a child of i, then it is not a cycle.
        
        # Let's say parent of i is safe
        # remove (i,j) from graphDict for child node j
        
        # Do so for all child of i, so that graphDict[i] has no more result 
        # (no more outgoing edges)
        
        #  Need to check all incoming edges though?
        
        # Just because its children are safe doesn't mean parent is safe.
        # The reverse is not true. If even one of its children is not safe, the 
        # parent is not safe. -> So if all children are safe, parent is safe.
        
        # Node j (child) is safe and in queue
        # i in reverseGraphDict[j], so remove (i,j) from graphDict
        # Loop. If all (i,j) is removed from graphDict, so 
        # graphDict[i] contains empty set(), then parent is also successfully safe.
        
        #    0     1    2   3   4   5  6      all parents
        # [[1,2],[2,3],[5],[0],[5],[],[]]    all children     
        
        N = len(graph)
        safe = [False] * N

        graph = list(map(set, graph))
        rgraph = [set() for _ in range(N)]
        q = collections.deque()

        for i, js in enumerate(graph):
            if not js:
                q.append(i)
            for j in js:
                rgraph[j].add(i)

        while q:
            j = q.pop()
            safe[j] = True
            for i in rgraph[j]:
                graph[i].remove(j)
                if len(graph[i]) == 0:
                    q.append(i)

        return [i for i, v in enumerate(safe) if v]
        
        
        
        \"\"\"
        
        N = len(graph)
        safe = [False] * N
        
        graph = map(set,graph)
        for elem in graph:
            print(elem)
        reverseGraphDict = [set() for _ in range(N)]

        safeQueue = collections.deque()
        
        for parent, children in enumerate(graph):
            # If there is no children (empty[]), terminal node
            if not children:
                safeQueue.append(parent)
                
            for child in children:
                # Don't do dfs here
                reverseGraphDict[child].add(parent) # a child can have multiple parents\"\"\"
                
                
                
        while safeQueue:
            child = safeQueue.popleft()
            safe[child] = True
            for parent in reverseGraphDict[child]:
                graph[parent].remove(child)
                
                # Parent is safe too, so push it into queue
                if len(graph[parent]) == 0:
                    #safe[parent] = True # Wil be taken care at top of loop
                    safeQueue.append(parent)
                
        return [idx for idx, boolean in enumerate(safe) if boolean == True]
            
        \"\"\"
        # Try DFS. Use a set to keep track of nodes already seen
        seenSet = set()
        safeList = []
        
        # Add parent to seenSet
        # Iterate over all connections to children from parent
        # dfs for each of those connections
        
        def dfs(parent):
            nonlocal graph
            nonlocal seenSet
            
            if parent in seenSet: # Already discovered before
            
            seenSet.add(parent)
            
            for edge in graph:
                if edge[0] == parent:
                    dfs(edge[1])
            
        
        
        
        \"\"\"
        '''
        # Loop over all nodes in graph, make them their own group
        for edge in graph:
            parent = edge[0]
            
            # group.newGroup(parent)
        
        
        for edge in graph:
            parent = edge[0]
            child = edge[1]'''
            
            # group parent and child together
            
            # if child is already grouped with parent (cycle),
            # Those nodes in the group cannot be part of the answer.
            
            # But if the parent/child has only one connection to all 
            # the nodes within the group that has the cycle, that node
            # (though connect) is technically safe.
            
            

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(snode):
            if mem[snode] == 1:
                return True
            elif mem[snode] == 2:
                return False

            mem[snode] = 1
            for e in graph[snode]:
                if cycle(e):
                    return True
            mem[snode] = 2
            return False

        n = len(graph)
        ret = []
        mem = [0] * n
        for i in range(n):
            if not cycle(i):
                ret.append(i)
        return ret


class Solution:
    def __init__(self):
        self.safe_nodes = set()
        self.unsafe_nodes = set()
        
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        def is_safe(node, stack=[]):
            if (not graph[node]) or (node in self.safe_nodes):
                self.safe_nodes.add(node)
                return True
            elif node in self.unsafe_nodes:
                return False
            else:
                if node in stack:
                    self.unsafe_nodes |= set(stack)
                    return False
                stack.append(node)
                if all([is_safe(child) for child in graph[node]]):
                    self.safe_nodes.add(node)
                    stack.pop()
                    return True
                else:
                    self.unsafe_nodes.add(node)
                    stack.pop()
                    return False
        
        for node in range(len(graph)):
            is_safe(node)
        
        return sorted(list(self.safe_nodes))

from collections import defaultdict, deque
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        q = deque()
        ans = [False] * n
        
        graph_map = dict()
        r_graph_map = defaultdict(set)
        for i in range(n):
            graph_map[i] = set(graph[i])
            
            if not graph[i]:
                q.append(i)            
            for out in graph[i]:
                r_graph_map[out].add(i)
        
        while q:
            safe_i = q.popleft()
            ans[safe_i] = True
            for in_id in r_graph_map[safe_i]:
                graph_map[in_id].remove(safe_i)
                if len(graph_map[in_id]) == 0:
                    q.append(in_id)
        return [i for i, safe in enumerate(ans) if safe]


import queue

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        \"\"\"
        Obs:
        1. Clearly, each note that belongs to the cycle is wrong
        If node is a leaf (terminal node), then it's eventually safe.
        If we remove this node, some other nodes might become leaves, if so, they are eventuall safe as well
        \"\"\"
        
        # We need transposition of the graph (directed graph with reversed edges), to be able to decrease out_deg for out predecessors
        graph_t = [[] for _ in range(len(graph))]
        for origin, adj_list in enumerate(graph):
            for dest in adj_list:
                graph_t[dest].append(origin)
        
        deg_out = [0 for _ in range(len(graph))]
        deg_out = [len(adj_list) for adj_list in graph]
        
        terminal_nodes = queue.Queue()
        for terminal_node in [node for node, d_out in enumerate(deg_out) if d_out == 0]:
            terminal_nodes.put(terminal_node)
        res = []
        while not terminal_nodes.empty():
            node = terminal_nodes.get()
            for dest in graph_t[node]:
                deg_out[dest] -= 1
                if deg_out[dest] == 0:
                    terminal_nodes.put(dest)
            
            res.append(node)
        
        return sorted(res)
        

from collections import deque

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        N = len(graph)
        
        graph = list(map(set,graph)) # fr -> tos
        rgraph=[set() for _ in range(N)] # to -> frs
        safe = [False]*N
        
        # this will contain safe nodes (that are not pointed to)
        q=deque()
        
        for fr,tos in enumerate(graph):
            if not tos:
                # safe
                q.append(fr)
            for to in tos:
                rgraph[to].add(fr)
            
        while q:
            to = q.popleft()
            safe[to] = True
            for fr in rgraph[to]:
                graph[fr].remove(to)
                if not graph[fr]:
                    # safe after removal of a to that is safe
                    q.append(fr)
                    
        return [i for i,v in enumerate(safe) if v]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        SAFE, VISITED, UNSAFE = 1, 0, -1
        is_safe = [None] * len(graph)

        def explore(node):
            if not graph[node]:
                is_safe[node] = SAFE
                return

            if is_safe[node] == VISITED:
                is_safe[node] = UNSAFE  # detected cycle
                return

            if is_safe[node] == None:
                is_safe[node] = VISITED
                for child in graph[node]:
                    if is_safe[child] in [None, VISITED]:
                        explore(child)
                    if is_safe[child] == UNSAFE:
                        is_safe[node] = UNSAFE
                        return
                else:
                    is_safe[node] = SAFE
                    return
        
        for node in range(len(graph)):
            if is_safe[node] == None:
                explore(node)
        return [node for node in range(len(graph)) if is_safe[node] == SAFE]


import queue

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        \"\"\"
        Obs:
        1. Clearly, each note that belongs to the cycle is wrong
        If node is a leaf (terminal node), then it's eventually safe.
        If we remove this node, some other nodes might become leaves, if so, they are eventuall safe as well
        \"\"\"
        
        # We need transposition of the graph (directed graph with reversed edges), to be able to decrease out_deg for out predecessors
        graph_t = [[] for _ in range(len(graph))]
        for origin, adj_list in enumerate(graph):
            for dest in adj_list:
                graph_t[dest].append(origin)
        
        deg_out = [0 for _ in range(len(graph))]
        deg_out = [len(adj_list) for adj_list in graph]
        
        terminal_nodes = queue.Queue()
        for terminal_node in [node for node, d_out in enumerate(deg_out) if d_out == 0]:
            terminal_nodes.put(terminal_node)
        eventually_safe = [False for _ in range(len(graph))]
        while not terminal_nodes.empty():
            node = terminal_nodes.get()
            for dest in graph_t[node]:
                deg_out[dest] -= 1
                if deg_out[dest] == 0:
                    terminal_nodes.put(dest)
            
            eventually_safe[node] = True
        
        return [idx for idx in range(len(graph)) if eventually_safe[idx]]
        

class Solution:
  def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    cycle_nodes = set()
    safe_nodes = set()
    visited = set()
    
    def helper(node: int, visited: set) -> bool:
      if node in cycle_nodes:
        return False
      if node in safe_nodes:
        return True
      
      if node in visited:
        cycle_nodes.add(node)
        return False
      
      visited.add(node)
      
      for child in graph[node]:
        if helper(child, visited) is False:
          cycle_nodes.add(node)
          return False
      
      safe_nodes.add(node)
      return True
    
    ans = []
    for node in range(len(graph)):
      if helper(node, visited):
        ans.append(node)
    
    return ans
    
        
        
    
    
    # (0), (1, 2)
    # (0, 1), (2, 2, 3)
    # (0, 1, 2), (2, 3, 5)
    # ()


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        WHITE, GRAY, BLACK = 0, 1, 2
        color = collections.defaultdict(int)
        
        def dfs(node):
            if color[node] != WHITE:
                return color[node] == BLACK
            
            color[node] = GRAY
            for next_node in graph[node]:
                if color[next_node] == BLACK:
                    continue
                if color[next_node] == GRAY or not dfs(next_node):
                    return False
            color[node] = BLACK
            return True
        
        return filter(dfs, range(len(graph)))

class Solution:
     def eventualSafeNodes(self, graph):
        def explore(i):
            visited[i] = 0
            for v in graph[i]:
                if visited[v] == 0 or (visited[v] == -1 and explore(v)): return True
            visited[i] = 1
            res.append(i)
            return False
        visited, res = [-1] * len(graph), []
        for i in range(len(graph)):
            if visited[i] == -1: explore(i)
        return sorted(res)
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        ev_safe = collections.deque()  # indicate eventually safe
        
        sgraph = defaultdict(set)  # The original graph, set version
        rgraph = defaultdict(set)  # So that we can removed it
        safe = [False]*len(graph)
        
        for i, nei in enumerate(graph):
            if not nei:
                ev_safe.append(i)
            for out in nei:
                rgraph[out].add(i)
                sgraph[i].add(out)
        
        # Start updating
        while ev_safe:
            node_point2safe = ev_safe.popleft()
            safe[node_point2safe] = True
            for node in rgraph[node_point2safe]:
                graph[node].remove(node_point2safe)
                if len(graph[node]) == 0:
                    ev_safe.append(node)
        
        return [i for i, v in enumerate(safe) if v]
            


def f(x,y,ci,v):
    a=True
    for i in x[ci]:
        if i in v:
            if y[i]!=1:a=False
            continue
        v.add(i)
        y[i]=f(x,y,i,v)
        a=y[i] and a
    return a
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        l=len(graph)
        y=[-1 for i in range(l)]
        v=set()
        for i in range(l):
            if y[i]==-1:
                v.add(i)
                y[i]=f(graph,y,i,v)
        return [i for i in range(l) if y[i]]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        SAFE, VISITED, UNSAFE = 1, 0, -1
        is_safe = [None] * len(graph)

        def explore(node):
            if not graph[node]:
                is_safe[node] = SAFE
                return

            if is_safe[node] == VISITED:
                is_safe[node] = UNSAFE  # detected cycle
                return

            if is_safe[node] == None:
                is_safe[node] = VISITED
                for child in graph[node]:
                    explore(child)
                    if is_safe[child] == UNSAFE:
                        is_safe[node] = UNSAFE
                        return
                else:
                    is_safe[node] = SAFE
                    return
        
        for node in range(len(graph)):
            if is_safe[node] == None:
                explore(node)
        # print(is_safe)
        return [node for node in range(len(graph)) if is_safe[node] == SAFE]


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        def dfs(node, graph):
            nodes[node] = 1  ## mark as visiting 
            for child in graph[node]:
                if nodes[child] == 1: 
                    return False 
                if not nodes[child] and not dfs(child, graph):
                    return False 
            nodes[node] = 2 
            return True 
        
        nodes = [0 for _ in range(len(graph))]
        ans = [] 
        ## check if there is a cycle at each node in the graph 
        ## if there is a cycle then don't add to final list 
        ## to check if there is a cycle in directed graph, use 
        ## 3-coloring DFS 
        
        for node in range(len(graph)):
            if dfs(node, graph):
                ans.append(node)
                

        return ans
                
                    
            


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # to see start with the node, whether there is a cycle
        v = [0 for _ in range(len(graph))]
        ans = []
        
        def dfs(cur):
            if v[cur] == 1:
                return True
            if v[cur] == 2:
                return False
            v[cur] = 1
            for j in graph[cur]:
                if dfs(j):
                    return True
            v[cur] = 2
            return False
        
        for i in range(len(graph)):
            if dfs(i):
                continue
            else:
                ans.append(i)
        
        return ans        
    
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # table = collections.defaultdict(list)
        # for i in range(len(graph)):
        #     table[i] = graph[i]
        
        #寻找从一个点出发，是否有环
        def dfs(i):
            if color[i] == 1:
                return False
            elif color[i] == 2:
                # ans.append(i)
                return True
            elif color[i] == 0:
                color[i] = 1
                if graph[i]:
                    for j in graph[i]:
                        # dfs(j)
                        if not dfs(j):
                            return False
                color[i] = 2
                ans.append(i)
                return True
                
                
        ans = []
        color = [0] * len(graph)
        for i in range(len(graph)):
            if color[i] == 0:
                dfs(i)
        return sorted(ans)
            
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        n = len(graph)
        
        out_degree = [0] * n
        
        in_nodes = collections.defaultdict(list) 
        term_nodes = []
        
        for i in range(n):
            
            out_degree[i] = len(graph[i])
            
            if out_degree[i] == 0: 
                term_nodes.append(i)
                
            for j in graph[i]: 
                in_nodes[j].append(i) 
                
        #print(f'out_degree:{out_degree}') #out_degree:[2, 2, 1, 1, 1, 0, 0]
        #print(f'in_nodes:{in_nodes}')  
        #in_nodes:defaultdict(<class 'list'>, {1: [0], 2: [0, 1], 3: [1], 5: [2, 4], 0: [3]})
        #print(f'term_nodes:{term_nodes}')   #term_nodes:[5, 6]

                      
        for term_node in term_nodes:
            for in_node in in_nodes[term_node]:
                
                out_degree[in_node] -= 1
                
                if out_degree[in_node] == 0: 
                    term_nodes.append(in_node)
                    
        return sorted(term_nodes)


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        n = len(graph)
        out_degree = collections.defaultdict(int)
        in_nodes = collections.defaultdict(list) 
        queue = []
        ret = []
        for i in range(n):
            out_degree[i] = len(graph[i])
            if out_degree[i]==0:
                queue.append(i)
            for j in graph[i]:
                in_nodes[j].append(i)  
        while queue:
            term_node = queue.pop(0)
            ret.append(term_node)
            for in_node in in_nodes[term_node]:
                out_degree[in_node] -= 1
                if out_degree[in_node]==0:
                    queue.append(in_node)
        return sorted(ret)


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:    
        WHITE, GREY, BLACK = 0, 1, 2
        color = collections.defaultdict(int)
        
        def dfs(u):
            if color[u] != WHITE:
                return color[u] != GREY
            
            color[u] = GREY
            for v in graph[u]:
                if color[v] == BLACK:
                    continue
                if color[v] == GREY or not dfs(v):
                    return False
                
            color[u] = BLACK
            
            return True
        
        return list(filter(dfs, range(len(graph))))

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        colour = [-1]*n
        
        def dfs(u):
            if colour[u]!=-1:
                colour[u]=1
            
            colour[u]=0
            for nei in graph[u]:
                if colour[nei]==1:
                    continue
                if colour[nei]==0 or not dfs(nei):
                    return False
            colour[u]=1
            return True
        
        return list(filter(dfs, list(range(n))))
                
            
        
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        result = []
        indegree = [len(edge) for edge in graph]
        neighbors = collections.defaultdict(list)
        for i, edge in enumerate(graph):
            for j in edge:
                neighbors[j].append(i)
        queue = []
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)
        while queue:
            i = queue.pop(0)
            result.append(i)
            for neighbor in neighbors[i]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
        return sorted(result)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        ans = []
        if len(graph) == 0:
            return ans
        status = [0 for _ in range(len(graph))]
        for i in range(len(graph)):
            if status[i] == 0:
                self.dfs(i, graph, status, ans)
        for i in range(len(graph)):
            if status[i] == 2:
                ans.append(i)
        return ans
                
    
    def dfs(self, i, graph, status, ans):
        status[i] = 1
        for neighbor in graph[i]:
            if status[neighbor] == 1:
                return False
            if status[neighbor] == 0 and not self.dfs(neighbor, graph, status, ans):
                return False
        
        status[i] = 2
        return True

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0] * n
        def dfs(node):
            if color[node]:
                return color[node] == 2
            color[node] = 1
            for nbor in graph[node]:
                if not dfs(nbor):
                    return False
            color[node] = 2
            return True
        return [node for node in range(n) if dfs(node)]

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def explore(i):
            visited[i] = 0
            for v in graph[i]:
                if visited[v] == 0 or (visited[v] == -1 and explore(v)): return True
            visited[i] = 1
            res.append(i)
            return False
        
        visited, res = [-1] * len(graph), []
        
        for i in range(len(graph)):
            if visited[i] == -1: explore(i)
        return sorted(res)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:  
        # 0 = not processed     1 = processing     2 = processed
        
        def cycle(ind):
            if color[ind] == 1:
                return True   # true means that there is a cycle
            if color[ind] == 2:
                return False   # no cycle is present
            
            color[ind] = 1
            
            for node in graph[ind]:
                if cycle(node):
                    return True            
            color[ind] = 2
            return False
  
        
        n = len(graph)
        color = [0]*n  
        
        for i in range(len(graph)):
            cycle(i)     
        
        return [i for i in range(n) if color[i] == 2]
    
#     def helper(self, graph, index, visited, cache) -> bool:
#         if visited[index]:
#             return False
        
#         if len(graph[index]) == 0:
#             return True
        
#         if index in cache:
#             return cache[index]
        
#         visited[index] = True
#         safe = True
#         for v in graph[index]:
#             safe = safe and self.helper(graph, v, visited, cache)
#         visited[index] = False
        
#         cache[index] = safe
#         return safe
        
#     def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
#         result = []
#         cache = {}
#         for i in range(len(graph)):
#             visited = [False for node in graph]
#             if self.helper(graph, i, visited, cache):
#                 result.append(i)
#         return result


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def dfs(i):
            if color[i] != 0: return color[i]
            color[i] = 1
            if any(dfs(j)==1 for j in graph[i]):
                return color[i]
            color[i] = 2
            return color[i]
            
        color = collections.defaultdict(int)
            
        ans = []
        n = len(graph)
        for i in range(n):
            if dfs(i) == 2:
                ans.append(i)
                
        return ans
                


# 0: unknown, 1: visiting, 2: safe
from collections import defaultdict
class Solution:
    def eventualSafeNodes(self, graph):
        state = defaultdict(int)
        N = len(graph)
        def dfs(node):
            if state[node] != 0:
                return state[node] == 2
            state[node] = 1
            for nei in graph[node]:
                if state[nei] == 1 or not dfs(nei):
                    return False
            state[node] = 2
            return True
        return [node for node in range(N) if dfs(node)]


#
# @lc app=leetcode id=802 lang=python3
#
# [802] Find Eventual Safe States
#
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        size = len(graph)
        AVAILABLE = 0
        VISITING = 1
        VISITED = 2
        status = [AVAILABLE] * size
        def isSafe(source, res):
            if status[source] != AVAILABLE: 
                return status[source] == VISITED
            status[source] = VISITING
            for neighbour in graph[source]:
                if not isSafe(neighbour, res):
                    return False
            status[source] = VISITED
            res.append(source)
            return True
        res = []
        for node in range(size):
            isSafe(node, res)
        return sorted(res)



from collections import defaultdict

class Solution:
    def eventualSafeNodes(self, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(set)
        inv = defaultdict(set)
        N = len(edges)
        ret = set()
        
        for s, es in enumerate(edges):
            for e in es:
                graph[s].add(e)
                inv[e].add(s)
        
        for n in range(N):
            if len(graph[n]) == 0: ret.add(n)
        
        todo = set(ret)
        
        while todo:
            pending = set()
            for n in todo:
                for s in inv[n]:
                    if graph[s].issubset(ret):
                        ret.add(s)
                        pending.add(s)
            todo = pending
        
        return sorted(ret)

from typing import List, Dict, Set
from collections import defaultdict

def find_safe_nodes(graph: Dict, rev_graph: Dict):
    outcount_nodes = defaultdict(set)
    for node, list_innodes in list(graph.items()):
        count_outedges = len(list_innodes)
        outcount_nodes[count_outedges].add(node)

    safe_nodes = set()
    while len(outcount_nodes[0]) > 0:
        safe_node = outcount_nodes[0].pop()
        safer_nodes = rev_graph[safe_node]
        for safer_node in safer_nodes:
            prev_outcount = len(graph[safer_node])
            graph[safer_node].remove(safe_node)
            outcount_nodes[prev_outcount].remove(safer_node)
            outcount_nodes[prev_outcount - 1].add(safer_node)
        safe_nodes.add(safe_node)
    return safe_nodes

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        list_graph = graph
        graph = defaultdict(set)
        rev_graph = defaultdict(set)

        for node1, list_node2 in enumerate(list_graph):
            for node2 in list_node2:
                graph[node1].add(node2)
                rev_graph[node2].add(node1)

        for i in range(len(list_graph)):
            if i not in graph:
                graph[i] = set()
            if i not in rev_graph:
                rev_graph[i] = set()

        safe_nodes = find_safe_nodes(graph, rev_graph)
        return sorted(safe_nodes)

s = Solution()

print((s.eventualSafeNodes(graph = [[1,2],[2,3],[5],[0],[5],[],[]])))
print((s.eventualSafeNodes(graph = [[1,2],[2,3],[5],[0],[5],[],[]]) == [2,4,5,6]))

print((s.eventualSafeNodes([[],[0,2,3,4],[3],[4],[]])))
print((s.eventualSafeNodes([[],[0,2,3,4],[3],[4],[]]) == [0, 1, 2, 3, 4]))




import collections\r
class Solution:\r
    def eventualSafeNodes(self, graph):\r
        q = collections.deque()\r
        outdegree = [0]*len(graph)\r
        income_node = collections.defaultdict(list)\r
        result = []\r
        for i in range(len(graph)):\r
            outdegree[i] = len(graph[i])\r
            if outdegree[i] == 0:\r
                q.append(i)\r
                continue\r
            for next_node in graph[i]:\r
                income_node[next_node].append(i)\r
        \r
        while q:\r
            node = q.popleft()\r
            result.append(node)\r
            for pre_node in income_node[node]:\r
                outdegree[pre_node] -= 1\r
                if outdegree[pre_node] == 0:\r
                    q.append(pre_node)\r
        \r
        return sorted(result)\r
\r
def __starting_point():\r
    sol = Solution()\r
    graph = [[1,2],[2,3],[5],[0],[5],[],[]]\r
    sol.eventualSafeNodes(graph)\r
\r
\r
\r
        \r
\r
                \r
\r
\r
        
__starting_point()

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        #Alternate solution to white gray black
        
        # white - not visited
        # grey - currently visiting
        # black - completely visited (so that we don't repeat it)
        
        unsafe_nodes = set()
        
        safe_nodes = set()
        
        def dfs(node, visited):
            if node in visited:
                return False
            
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor in unsafe_nodes:
                    unsafe_nodes.add(node)
                    return False
                if neighbor in safe_nodes:
                    continue
                if not dfs(neighbor, visited):
                    unsafe_nodes.add(node)
                    return False
     
            safe_nodes.add(node)
            return True
        
        for i in range(len(graph)):
            dfs(i,set())
                
        return list(sorted(safe_nodes))

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        parent_g=collections.defaultdict(list)
        visited=set()
        queue=[]
        for i in range(len(graph)):
            if len(graph[i])==0:
                queue.append(i)
            for c in graph[i]:
                parent_g[c].append(i)
        while(queue):
            current=queue.pop(0)
            flag=True
            for c in graph[current]:
                if not c in visited:
                    flag=False
                    break
            if flag:
                visited.add(current)
                for p in parent_g[current]:
                    if not p in visited:
                        queue.append(p)
        return sorted(list(visited))
                


class Solution:
    # if cycle then not safe else safe
        # we can tell if there's a cycle by keeping track of visited for all paths eminating from node
    # DP: keep track of set of nodes that are not safe so that if we see it again we know not safe automatically
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        ans, dp, visited = [], {}, set()
        
        def dfs_visit(i):
            if i in visited: return False
            if i in dp: return dp[i]
            visited.add(i)
            valid = True
            if graph[i]:
                valid = all([ dfs_visit(j) for j in graph[i] ])
            visited.remove(i)
            dp[i] = valid
            return valid
        
        
        for i in range(len(graph)):
            if dfs_visit(i):
                ans.append(i)
        return ans
    
    
    
    
    
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        w,g,b = 0,1,2
        color = collections.defaultdict(int)
        def dfs(node):
            if color[node] != w:
                return color[node] == b
            color[node] = g
            for child in graph[node]:
                if color[child] == b:
                    continue
                elif color[child] == g or not dfs(child):
                    return False
            color[node] = b
            return True
        ans = []
        for i in range(len(graph)):
            if dfs(i) == True:
                ans.append(i)
        return ans

class Solution:
  def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    n = len(graph)
    state = [-1] * n # -1 = unvisited, 0 = involved in directed cycle, 1 = eventually safe
    result = []
    
    def dfs(node):
      state[node] = 0 # may be involved in a cycle
      for adj in graph[node]:
        if state[adj] == 0 or (state[adj] == -1 and dfs(adj)):
          return True
      state[node] = 1
      result.append(node)
    
    for i in range(n):
      if state[i] == -1:
        dfs(i)
    
    return sorted(result)
    


import collections 

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        WHITE, GRAY, BLACK = 0, 1,2
        color_of_nodes = collections.defaultdict(int)
        def dfs(node):
            if color_of_nodes[node] != WHITE:
                return color_of_nodes[node] == BLACK 
            
            color_of_nodes[node] = GRAY
            for nei in graph[node]:
                if color_of_nodes[nei] == GRAY or not dfs(nei):
                    return False 
            color_of_nodes[node] = BLACK
            return True
        
        res = []
        for i, node in enumerate(graph):
            if dfs(i):
                res.append(i)
        return res 
                    
                
        
    


class Solution(object):
    def eventualSafeNodes(self, graph):
        N = len(graph)
        T = set([n for n in range(N) if not graph[n]])
        V = set()
        def dfs(node,visited):
            if node in T:
                return True
            if node in V or node in visited:
                return False
            visited.append(node)
            for n in graph[node]:
                if not dfs(n,visited):
                    V.add(node)
                    V.add(n)
                    return False
                else:
                    T.add(n)
            T.add(node)
            return True
        res = [n for n in range(N) if dfs(n,[])]
        return res

class Solution:
    def __init__(self):
        self.d = {}
        self.safe_nodes = {}
    
    def safe_finder(self, cur_node):
        if len(self.d[cur_node]) == 0:
            self.safe_nodes[cur_node] = True
            return True
        
        for n in self.d[cur_node]:
            print(cur_node,n)
            if n == cur_node:
                self.safe_nodes[cur_node] = False
                return False
            
            if n in self.safe_nodes.keys():
                if self.safe_nodes[n] == False:
                    self.safe_nodes[cur_node] = False
                    return False
            else:
                self.safe_nodes[n] = False
                tmp = Solution.safe_finder(self, n)
                if tmp == False:
                    self.safe_nodes[cur_node] = False
                    return False
        
        self.safe_nodes[cur_node] = True
        return True
                
            
        
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        for i in range(len(graph)):
            node = graph[i]
            self.d[i] = []
            for edge in node:
                self.d[i].append(edge)
        
        # print(self.d)
        for k in self.d.keys():
            Solution.safe_finder(self,k)
        
        answer = []
        for k,v in self.safe_nodes.items():
            if v == True:
                answer.append(k)
        
        return sorted(answer)

from collections import deque, defaultdict
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        N = len(graph)
        safe_states = [False] * N
        
        another_graph = defaultdict(set)
        q = collections.deque()
        
        for i, js in enumerate(graph):
            if not js:
                q.append(i)
            
            for j in js:
                another_graph[j].add(i)
        
        print((graph, another_graph))
        
        while q:
            u = q.popleft()
            safe_states[u] = True
            
            for v in another_graph[u]:
                graph[v].remove(u)
                
                if len(graph[v]) == 0:
                    q.append(v)
        
        return [u for u, v in enumerate(safe_states) if v]
        


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def cycle(ind):
            if color[ind] == 1:
                return True   # true means that there is a cycle
            if color[ind] == 2:
                return False   # no cycle is present
            
            color[ind] = 1
            
            for node in graph[ind]:
                if cycle(node):
                    return True            
            color[ind] = 2
            return False
  
        
        n = len(graph)
        color = [0]*n  
        
        for i in range(len(graph)):
            cycle(i)     
        
        return [i for i in range(n) if color[i] == 2]

from collections import deque
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def explore(i):   ##checks for cycle (true)
            colors[i] = 1
            for j in graph[i]:
                if ((colors[j]==0 and explore(j)) or colors[j] == 1):
                    return True
            colors[i] = 2
            res.append(i)
            return False
        colors = [0 for i in range(len(graph))]
        #0 - white, 1 - gray, 2 - black
        #0 - unvisited, 1 - under processing, 2 - visited
        res = []
        for i in range(len(graph)):
            if colors[i] == 0:
                explore(i)
        return sorted(res)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        g = dict(enumerate(graph))
        
        safe = [-1] * len(g)
        
        def dfs(v):
            if safe[v] >= 0:
                return safe[v]
            
            if v not in g:
                safe[v] = 0
                return 0
            
            children = g.pop(v)
            
            if all(map(dfs, children)):
                safe[v] = 1
                return 1
            
            safe[v] = 0
            return 0
        
        for i in range(len(g)):
            dfs(i)
        
        return [i for i, s in enumerate(safe) if s > 0]
                
            
            # if (1) all of my children are safe
            # if (2) 
            
            
            
        
        


class Solution:
    
    # Check each vertex to see if its part of a cycle
    # If it is, it is not a safe vertex.
    
    # All nodes in that cycle are not considered to be safe vertices
    
    # Nodes that have no directed edges are also considered to be safe.
    
    # A node is considered safe it all its edges are to nodes that will eventually
    # become safe. So it one edge points to a safe node, but the other edge points to a 
    # cycle, that node is stil considered unsafe.
    
    # Even union find fails algo? Yes. You can group up safe nodes with cycles
    # Union find helps you prevent cycles, but not this application.
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        # If parent node i has no incoming edges (i,j) where parent (k) of 
        # node j is also a child of i, then it is not a cycle.
        
        # Let's say parent of i is safe
        # remove (i,j) from graphDict for child node j
        
        # Do so for all child of i, so that graphDict[i] has no more result 
        # (no more outgoing edges)
        
        #  Need to check all incoming edges though?
        
        # Just because its children are safe doesn't mean parent is safe.
        # The reverse is not true. If even one of its children is not safe, the 
        # parent is not safe. -> So if all children are safe, parent is safe.
        
        # Node j (child) is safe and in queue
        # i in reverseGraphDict[j], so remove (i,j) from graphDict
        # Loop. If all (i,j) is removed from graphDict, so 
        # graphDict[i] contains empty set(), then parent is also successfully safe.
        
        #    0     1    2   3   4   5  6      all parents
        # [[1,2],[2,3],[5],[0],[5],[],[]]    all children     
        \"\"\"
        N = len(graph)
        safe = [False] * N

        graph = list(map(set, graph))
        rgraph = [set() for _ in range(N)]
        q = collections.deque()

        for i, js in enumerate(graph):
            if not js:
                q.append(i)
            for j in js:
                rgraph[j].add(i)

        while q:
            j = q.pop()
            safe[j] = True
            for i in rgraph[j]:
                graph[i].remove(j)
                if len(graph[i]) == 0:
                    q.append(i)

        return [i for i, v in enumerate(safe) if v]\"\"\"
        
        
        
        
        
        N = len(graph)
        safe = [False] * N
        
        graph = list(map(set,graph))
        print(graph)
        for elem in graph:
            print(elem)
        reverseGraphDict = [set() for _ in range(N)]

        safeQueue = collections.deque()
        
        for parent, children in enumerate(graph):
            # If there is no children (empty[]), terminal node
            if not children:
                safeQueue.append(parent)
                
            for child in children:
                # Don't do dfs here
                reverseGraphDict[child].add(parent) # a child can have multiple parents
                
                
                
        while safeQueue:
            child = safeQueue.popleft()
            safe[child] = True
            for parent in reverseGraphDict[child]:
                graph[parent].remove(child)
                
                # Parent is safe too, so push it into queue
                if len(graph[parent]) == 0:
                    #safe[parent] = True # Wil be taken care at top of loop
                    safeQueue.append(parent)
                
        return [idx for idx, boolean in enumerate(safe) if boolean == True]
            
        \"\"\"
        # Try DFS. Use a set to keep track of nodes already seen
        seenSet = set()
        safeList = []
        
        # Add parent to seenSet
        # Iterate over all connections to children from parent
        # dfs for each of those connections
        
        def dfs(parent):
            nonlocal graph
            nonlocal seenSet
            
            if parent in seenSet: # Already discovered before
            
            seenSet.add(parent)
            
            for edge in graph:
                if edge[0] == parent:
                    dfs(edge[1])
            
        
        
        
        \"\"\"
        '''
        # Loop over all nodes in graph, make them their own group
        for edge in graph:
            parent = edge[0]
            
            # group.newGroup(parent)
        
        
        for edge in graph:
            parent = edge[0]
            child = edge[1]'''
            
            # group parent and child together
            
            # if child is already grouped with parent (cycle),
            # Those nodes in the group cannot be part of the answer.
            
            # But if the parent/child has only one connection to all 
            # the nodes within the group that has the cycle, that node
            # (though connect) is technically safe.
            
            

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        m = len(graph)
        color = [0] * m
        def dfs(i):
            if color[i]:
                return color[i] == 1
            color[i] = 2
            for n in graph[i]:
                if not dfs(n):
                    return False
            color[i] = 1
            return True
        output = []
        for i in range(m):
            if dfs(i):
                output.append(i)
        return output

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        colour = [0] * len(graph)
        def dfs(i):
            if colour[i] != 0:
                return colour[i] == 2

            colour[i] = 1
            for c in graph[i]:
                if not dfs(c):
                    return False
            colour[i] = 2
            return True

        for node in range(len(graph)):
            dfs(node)
        return [i for i in range(len(graph)) if colour[i] == 2]


import collections
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        res = []
        visited = collections.defaultdict(int)
        N = len(graph)
        for i in range(N):
            if self.dfs(graph, i, visited):
                res.append(i)
        return res
    
    def dfs(self, graph, node, visited):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True
        visited[node] = 1
        for n in graph[node]:
            if not self.dfs(graph, n, visited):
                return False
        visited[node] = 2
        return True

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0 for _ in range(n)] # 0 white, 1 gray, 2 black
        res = []
        for node_index in range(n):
            if self.dfs(graph, index=node_index, color=color):
                res.append(node_index)
        return res
            
    
    def dfs(self, graph, index, color):
        if color[index] > 0:
            return color[index] == 2
        
        color[index] = 1
        
        for j in graph[index]:
            if color[j] == 2:
                continue
            elif color[j] == 1 or not self.dfs(graph, j, color):
                return False
        
        color[index] = 2
        return True


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # BFS
        safe = [False] * len(graph)
        rev = [set() for _ in range(len(graph))]
        queue = collections.deque()
        
        for i, nodes in enumerate(graph):
            if not nodes:
                queue.append(i)
            else:
                for node in nodes:
                    rev[node].add(i)
        
        while queue:
            curr = queue.popleft()
            safe[curr] = True
            for j in rev[curr]:
                graph[j].remove(curr)
                if len(graph[j]) == 0:
                    queue.append(j)
        return [i for i, val in enumerate(safe) if val]
        
        
        # DFS
#         W, G, B = 0, 1, 2     # gray: entry; black: exit
#         color = collections.defaultdict(int)
        
#         def dfs(node):
#             if color[node] == G:
#                 return False
#             if color[node] == B:
#                 return True
            
#             color[node] = G
#             for nei in graph[node]:
#                 if color[nei] == B:
#                     continue
#                 if color[nei] == G or not dfs(nei):
#                     return False
                
#             color[node] = B
#             return True
            
        
#         res = []
#         for i in range(len(graph)):
#             if dfs(i): res.append(i)
#         return res


class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        seen, safe = set(), set()
        def dfs(u):
            if u in seen: return u in safe
            seen.add(u)
            if all(dfs(v) for v in graph[u]): safe.add(u); return True
        return list(filter(lambda u: dfs(u), range(len(graph))))

class Solution:
    
    # Check each vertex to see if its part of a cycle
    # If it is, it is not a safe vertex.
    
    # All nodes in that cycle are not considered to be safe vertices
    
    # Nodes that have no directed edges are also considered to be safe.
    
    # A node is considered safe it all its edges are to nodes that will eventually
    # become safe. So it one edge points to a safe node, but the other edge points to a 
    # cycle, that node is stil considered unsafe.
    
    # Even union find fails algo? Yes. You can group up safe nodes with cycles
    # Union find helps you prevent cycles, but not this application.
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        # If parent node i has no incoming edges (i,j) where parent (k) of 
        # node j is also a child of i, then it is not a cycle.
        
        # Let's say parent of i is safe
        # remove (i,j) from graphDict for child node j
        
        # Do so for all child of i, so that graphDict[i] has no more result 
        # (no more outgoing edges)
        
        #  Need to check all incoming edges though?
        
        # Just because its children are safe doesn't mean parent is safe.
        # The reverse is not true. If even one of its children is not safe, the 
        # parent is not safe. -> So if all children are safe, parent is safe.
        
        # Node j (child) is safe and in queue
        # i in reverseGraphDict[j], so remove (i,j) from graphDict
        # Loop. If all (i,j) is removed from graphDict, so 
        # graphDict[i] contains empty set(), then parent is also successfully safe.
        
        #    0     1    2   3   4   5  6      all parents
        # [[1,2],[2,3],[5],[0],[5],[],[]]    all children     
        \"\"\"
        N = len(graph)
        safe = [False] * N

        graph = list(map(set, graph))
        rgraph = [set() for _ in range(N)]
        q = collections.deque()

        for i, js in enumerate(graph):
            if not js:
                q.append(i)
            for j in js:
                rgraph[j].add(i)

        while q:
            j = q.pop()
            safe[j] = True
            for i in rgraph[j]:
                graph[i].remove(j)
                if len(graph[i]) == 0:
                    q.append(i)

        return [i for i, v in enumerate(safe) if v]\"\"\"
        
        
        
        
        
        N = len(graph)
        safe = [False] * N
        
        graph = list(map(set,graph))
        print(graph)
        for elem in graph:
            print(elem)
        reverseGraphDict = [set() for _ in range(N)]

        safeQueue = collections.deque()
        
        for parent, children in enumerate(graph):
            # If there is no children (empty[]), terminal node
            if not children:
                safeQueue.append(parent)
                
            for child in children:
                # Don't do dfs here
                reverseGraphDict[child].add(parent) # a child can have multiple parents
                
                
                
        while safeQueue:
            child = safeQueue.pop()
            safe[child] = True
            for parent in reverseGraphDict[child]:
                graph[parent].remove(child)
                
                # Parent is safe too, so push it into queue
                if len(graph[parent]) == 0:
                    #safe[parent] = True # Wil be taken care at top of loop
                    safeQueue.append(parent)
                
        return [idx for idx, boolean in enumerate(safe) if boolean == True]
            
        \"\"\"
        # Try DFS. Use a set to keep track of nodes already seen
        seenSet = set()
        safeList = []
        
        # Add parent to seenSet
        # Iterate over all connections to children from parent
        # dfs for each of those connections
        
        def dfs(parent):
            nonlocal graph
            nonlocal seenSet
            
            if parent in seenSet: # Already discovered before
            
            seenSet.add(parent)
            
            for edge in graph:
                if edge[0] == parent:
                    dfs(edge[1])
            
        
        
        
        \"\"\"
        '''
        # Loop over all nodes in graph, make them their own group
        for edge in graph:
            parent = edge[0]
            
            # group.newGroup(parent)
        
        
        for edge in graph:
            parent = edge[0]
            child = edge[1]'''
            
            # group parent and child together
            
            # if child is already grouped with parent (cycle),
            # Those nodes in the group cannot be part of the answer.
            
            # But if the parent/child has only one connection to all 
            # the nodes within the group that has the cycle, that node
            # (though connect) is technically safe.