207. Course Schedule

NO IMAGE

題目:
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:
每一層都是找出當前不需要prerequisite的課程,即等級為0的課程,當掃到這門課裡,把其他需要這門課作為prerequisite的課降一個等級,直到其等級為0時,把它存到queue中作為其他課程可用的prerequisite課。同時記錄一共存了多少課程在queue裡,這些課都是可以上的課。

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]]  ;
graph[course[0]].add(course[1]);
}
//BFS
Queue<Integer> q = new LinkedList<>();
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:
這裡把每個點分三種狀態:0-沒訪問,1-正在訪問,2-訪問結束。每一個點都掃透了,確定這個點跟其他點不會構成deadlock,那麼把這個點跟其所有的子結都標成2-訪問結束。如果當兩個點在同時訪問的時候,那麼構成死迴圈,返回false。掃完所有的點都沒問題,才返回true。

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) {
graph[course[0]].add(course[1]);
}
//DFS
int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i  ) {
if (visited[i] == 2) continue;
if (!DFS(graph, i, visited)) {
return false;
}
}
return true;
}