There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

&nbsp;
Example 1:

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

Example 2:

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


&nbsp;
Constraints:


	n == graph.length
	1 &lt;= n &lt;= 104
	0 &lt;= graph[i].length &lt;= n
	0 &lt;= graph[i][j] &lt;= n - 1
	graph[i] is sorted in a strictly increasing order.
	The graph may contain self-loops.
	The number of edges in the graph will be in the range [1, 4 * 104].


import collections

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

        n = len(graph)
        ans = []
        
        for i in range(n):
            if not graph[i]:
                ans.append(i)
        
        def loop(key, loops):
    
            loops.append(key)
            for i in graph[key]:
                if i in loops:
                    return False
                elif i in ans: 
                    continue
                else:
                    r = loop(i, loops)
                    if r == True: 
                        continue
                    else: 
                        return False

            idx = loops.index(key)
            loops.pop(idx)
            return True
                    
        for i in range(n):
            loops = []
            if i in ans:
                continue
            r = loop(i, loops)
            if r == True: ans.append(i)
 
        return sorted(ans)
class Solution {
   public List<Integer> eventualSafeNodes(int[][] graph) {
    int n=graph.length;
    List<Integer> ans=new ArrayList<>();

    boolean visited[]=new boolean[n];
    boolean dfsVisited[]=new boolean[n];

    boolean nodeCycles[]=new boolean[n];

    for(int i=0;i<n;i++){
        if(visited[i]==false){
             isCycle(i,graph,dfsVisited,visited,nodeCycles);
        }
    }
    for(int i=0;i<nodeCycles.length;i++){
        if(nodeCycles[i]==false)
            ans.add(i);
    }
    return ans;
}

public boolean isCycle(int node,int graph[][],boolean dfsVisited[],boolean visited[],boolean [] nodeCycles) {
    visited[node]=true;
    dfsVisited[node]=true;

    for(int adjNode:graph[node]){
        if(visited[adjNode]==false){
           if(isCycle(adjNode,graph,dfsVisited,visited,nodeCycles))
                return nodeCycles[node]=true;
        }else if(visited[adjNode]==true && dfsVisited[adjNode]==true){
            return nodeCycles[node]=true;
        }
    }
    dfsVisited[node]=false;
    return false;
}
}
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<bool> vis(n, false), curr_vis(n, false), safe(n, true);

        for(int i=0; i<n; i++)
            if(!vis[i])
                dfs(i, vis, curr_vis, safe, graph);

        vector<int> ans;
        for(int i=0; i<n; i++)
            if(safe[i])
                ans.push_back(i);

        return ans;
    }

    bool dfs(int i, vector<bool> &vis, vector<bool> &curr_vis, vector<bool> &safe, vector<vector<int>>& graph){
        vis[i]=true, curr_vis[i]=true;

        for(auto j : graph[i]){
            if(!vis[j]){
                if(dfs(j, vis, curr_vis, safe, graph)==false)
                    return safe[i] = false;
            }
            else if(curr_vis[j])
                return safe[i] = false;
        }

        curr_vis[i]=false;
        return safe[i];
    }
};
/**
 * @param {number[][]} graph
 * @return {number[]}
 */
var eventualSafeNodes = function(graph) {
    const ans = [];
    const map = new Map();
    for(let i=0; i<graph.length; i++) {
        if(dfs(graph, i, map)) {
            ans.push(i);
        }
    }
    return ans;
};

var dfs = function(graph, node, map) {
    if(map.has(node)) return map.get(node);
    map.set(node, false);
    for(let nei of graph[node]) {
        if(!dfs(graph, nei, map)) {
            return false;
        }
    }
    map.set(node, true);
    return true;
}
Find Eventual Safe States