# 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){
}
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;
}
}
``````