Course Schedule Leetcode


#1

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

#2

A version of topological sort that checks whether all courses can be completed.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean courseFinishable = true;
        boolean[] visited = new boolean[numCourses];
        boolean[] greySet = new boolean[numCourses];
        List[] pre = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++){
            pre[i] = new ArrayList<Integer>();
        }
        for (int[] p : prerequisites){
            pre[p[0]].add(p[1]);
        }
        for(int i=0;i<numCourses;i++){
          courseFinishable = courseFinishable && helper(i, pre, greySet, visited);
        }
        return courseFinishable;
    }
    
    public boolean helper(int course, List[] pre, boolean[] greySet, boolean[] visited){
        if(visited[course]){
            return true;
        } else if(greySet[course]){
            return false;
        } else{
            greySet[course] = true;
        }
        
        for (int j = 0; j < pre[course].size(); j++){
            int newCourse = (int)pre[course].get(j);
            if(!helper(newCourse, pre, greySet, visited)){return false;}
        }
        
        visited[course]=true;
        
        return true;
    }
}