0802 Find Eventual Safe States

0802 Find Eventual Safe States.java

class Solution {    
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] vis = new int[n];
        int[] path = new int[n];
        List<Integer> res = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {
                dfs(i, graph, vis, path);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (path[i] == 0) {
                res.add(i);
            }
        }
        
        return res;
    }
    
    private boolean dfs(int curr, int[][] graph, int[] vis, int[] path) {
        vis[curr] = 1;
        path[curr] = 1;
        
        for (int u : graph[curr]) {
            if (vis[u] == 0) {
                if (dfs(u, graph, vis, path)) {
                    return true;
                }
            } else if (path[u] == 1) {
                return true;
            }
        }
        
        path[curr] = 0;
        return false;
    }
}