Easy DFS solution beats 99%


  • 1
    I
    public boolean canFinish(int numCourses, int[][] prerequisites){
        ArrayList[] graph = new ArrayList[numCourses];
        for(int i=0;i<numCourses;i++)
            graph[i] = new ArrayList();
    
        int[] visited = new int[numCourses];
        for(int i=0; i<prerequisites.length;i++){
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
    
        for(int i=0; i<numCourses; i++){
            if(!dfs(graph,visited,i))
                return false;
        }
        return true;
    }
    
    private boolean dfs(ArrayList[] graph, int[] visited, int course){
        if(visited[course] == -1)
            return false;
        if(visited[course] == 1)
            return true;
        visited[course] = -1;
        for(int i=0; i<graph[course].size();i++){
            if(!dfs(graph,visited,(int)graph[course].get(i)))
                return false;
        }
        visited[course] = 1;
        return true;
    }

Log in to reply
 

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