Straightforward Java DFS solution, beats 99%


  • 0
    S

    '''
    int index = 0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] res = new int[numCourses];
    List[] graph = new ArrayList[numCourses];

        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0; i < prerequisites.length; i++){
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        
        int[] visited = new int[numCourses];
        
        for(int i = 0; i < numCourses; i++){
            if(visited[i] == 0){
                if(!dfs(res, i, graph, visited)){
                    return new int[0];
                };
            }
        }
        return res;
    }
    
    public boolean dfs(int[] res, int course, List[] graph, int[] visited){
        visited[course] = 1; //course is being visited
        
        for(int i = 0; i < graph[course].size(); i++){
            if(visited[(int)graph[course].get(i)] == 1){  //cycle detected
                return false;
            }
            
            if(visited[(int)graph[course].get(i)] == 0){
                if(!dfs(res, (int)graph[course].get(i), graph, visited)){ //go to find prerequisite for graph[course].get(i)
                    return false;
                };
            }
        }
        
        visited[course] = 2;
        res[index++] = course; //add current course to the list. 
        
        return true;
    }
    

    '''


Log in to reply
 

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