Java dfs solution


  • -1
    L
    public boolean canFinish(int numCourses, int[][] pres) {
        List<Integer> [] graph = new List[numCourses];
        for(int i = 0; i < graph.length; i++){
            graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < pres.length; i++){
            graph[pres[i][1]].add(pres[i][0]);
        }
        int[] vis = new int[numCourses];
        for(int i = 0; i < graph.length; i++){
            if(vis[i] != 1){
                if(!dfs(graph,i,vis)) return false;
            }
        }
        return true;
    }
    boolean dfs(List<Integer>[] graph,int u,int[] vis){
        vis[u] = -1;
        for(int i = 0; i < graph[u].size(); i++){
            if(vis[graph[u].get(i)] == -1) return false;
            if(!dfs(graph,graph[u].get(i),vis)) return false;
        }
        vis[u] = 1;
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.