There are a total of n courses you have to take, labeled from
0ton - 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.
大致意思就是给定我们一定数量的课程，以及课程间的先修关系，让我们判断是否可以修完所有课程。
该问题等价于判断一个有向图是否有环，如果有环，就无法对该有向图进行拓扑排序，也就无法在满足课程间的先修关系的前提下修完所有课程。
我们可以依次从每个顶点开始使用DFS进行图的搜索，一旦发现环即可断定无法修完所有课程。为了提高效率，本算法加了一个回溯拆边的操作，因为既然已经确认这条路径上没有环，就不需要重复访问了。
代码如下：
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
boolean[] visited = new boolean[numCourses]; // 访问标志
List<Integer>[] adj = new List[numCourses]; // 邻接链表
for(int i = 0; i < numCourses; i++)
adj[i] = new ArrayList<Integer>();
for(int i = 0; i < prerequisites.length; i++) // 由偏序关系构造邻接链表
{
int curCourse = prerequisites[i][0];
int preCourse = prerequisites[i][1];
adj[preCourse].add(curCourse);
}
for(int i = 0; i < numCourses; i++) // 从每一个结为起点开始做DFS，每次循环visited数组元素均为false
{
if(!dfs(adj, visited, i)) // 任意一次DFS发现环均可断定无法修完所有课程
return false;
}
return true;
}
private boolean dfs(List<Integer>[] adj, boolean[] visited, int course){
if(visited[course]) // 再次访问访问过的结点，有环
return false;
visited[course] = true;
for (int i = 0; i < adj[course].size(); i++)
{
if(!dfs(adj, visited, adj[course].get(i)))
return false;
adj[course].remove(i); // 未发现环，依次拆掉走过的边，避免再走这条路
}
visited[course] = false; // 标志复位，向上回溯
return true;
}
}
解决本题的另一种方法是使用BFS，以无需先修的课程为起点，根据课程间的偏序关系搜索其他课程，统计搜索到（修完）的课程数，与总课程数进行比较即可判断是否可以修完所有课程，代码如下：
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] adj = new List[numCourses]; // 邻接链表
for(int i = 0; i < numCourses; i++)
adj[i] = new ArrayList<Integer>();
int[] indegree = new int[numCourses]; // 入度，即所需先修课程数
Queue<Integer> readyCourses = new LinkedList(); // 可修课程队列
int finishCount = 0; // 修完的课程数
for (int i = 0; i < prerequisites.length; i++) // 由偏序关系构造邻接链表，并统计入度
{
int curCourse = prerequisites[i][0];
int preCourse = prerequisites[i][1];
adj[preCourse].add(curCourse);
indegree[curCourse]++;
}
for (int i = 0; i < numCourses; i++)
{
if (indegree[i] == 0)
readyCourses.offer(i); // 无需先修的课程先入队列
}
while (!readyCourses.isEmpty())
{
int course = readyCourses.poll(); // 出队列，即修完该课程
finishCount++;
for (int nextCourse : adj[course])
{
indegree[nextCourse]--;
if (indegree[nextCourse] == 0) // 所有先修课程已修完，入队列
readyCourses.offer(nextCourse);
}
}
return finishCount == numCourses;
}
}