# 207. Course Schedule

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?

For example:

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

2, [[1,0],[0,1]]
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:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

BFS:

``````public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 1) return true;
if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;
ArrayList[] graph = new ArrayList[numCourses];
int[] degree = new int[numCourses];
for (int i = 0; i < numCourses; i  ) {
graph[i] = new ArrayList();
}
for (int[] course : prerequisites) {
degree[course[1]]  ;
}
//BFS
int courseRemaining = numCourses;
for (int i = 0; i < numCourses; i  ) {
if (degree[i] == 0) {
q.offer(i);
courseRemaining--;
}
}
//Search one and get rid of this one for the all
while(!q.isEmpty()) {
int key = q.poll();
for (int i = 0; i < graph[key].size(); i  ) {
int course = (int)graph[key].get(i);
degree[course]--;
if (degree[course] == 0) {
q.offer(course);
courseRemaining--;
}
}
}
return courseRemaining == 0;
}``````

DFS:

``````public boolean DFS(ArrayList[] graph, int course, int[] visited) {
//set 0 as not visited, 1 as visiting, 2 as visited
visited[course] = 1;
for (int i = 0; i < graph[course].size(); i  ) {
int curtCourse = (int)graph[course].get(i);
if (visited[curtCourse] == 1) { //if curtCourse is visiting as well, it's a circle
return false;
} else if (visited[curtCourse] == 0) { //if curtCourse hasn't visited yet, go and visit
visited[curtCourse] = 1;
//這裡總是忘記，當dfs中case return false時，才return false, 否則繼續迴圈
if(!DFS(graph, curtCourse, visited)) {
return false;
}
}
}
visited[course] = 2;
return true;
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 1) return true;
if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;
ArrayList[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i  ) {
graph[i] = new ArrayList();
}
for (int[] course : prerequisites) {