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.
Analysis
基本思路：
- 循环所有的sink vertex (没有outgoing的edge)放入queue,记录标记count（count初始化为vertex数量）
- 去掉这个sink vertex和与之相连的edge，找到下一个sink vertex，放入queue，记录标记为--count
- 最后看看是不是所有的vertex都能标记（count==0）
Code
public boolean canFinish(int numCourses, int[][] prerequisites) {
//用来标记所有的edges
//用来标记从每个点出去edges的个数
int[][] matrix = new int[numCourses][numCourses]; // i -> j
int[] indegree = new int[numCourses];
for (int i=0; i<prerequisites.length; i++) {
int ready = prerequisites[i][0];
int pre = prerequisites[i][1];
if (matrix[pre][ready] == 0)
indegree[ready]++; //duplicate case
matrix[pre][ready] = 1;
}
int count = numCourses;
Queue<Integer> queue = new LinkedList();
//把所有没有outgoing edge的vertex (sink vertex)都放到queue里面去
for (int i=0; i<indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
//情况一：如果queue是空的，说明没有vertex是sink vertex，那么肯定有cycle，不会进入while，return false
while (!queue.isEmpty()) {
int course = queue.poll();
//每找个一个sink vertex,count++，意思是已经可以标记它了
count--;
for (int i=0; i<numCourses; i++) {
//便利所有vertex，如果找到了一个和这个sink vertex course项链的vertex
if (matrix[course][i] != 0) {
//--indegree[i]==0，说明和它相连的那个点除去现在这个edge已经没有别的edge，说明它是下一个sink vertex
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
//count==numCourses说明可以标记所有点，那么一定是acyclic，如果不能标记，就一定有cycle
return count == 0;
}