共计 2237 个字符，预计需要花费 6 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。例如，想要学习课程 0，你需要先完成课程 1，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。示例 2:
输入: 2, [[1,0],[0,1]]输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
解答：利用图的拓扑排序。拓扑排序是来检测图中有无环的算法。具体步骤：1 找到一个入度为 0 的点，若没有，则返回图中有环。2 删除 1 中找到的点及以它为起点的边。3 重复 1、2 直到图中所有点都被删除，此时返回图中无环。
下面的一种思路是建立类似邻接表的图，这里的邻接表保存的不是边，而是指向该点的其他点，这种算法很好理解，但是时间复杂度过大。思想是，每一次都找到一个点，这个点没有任何点指向它。然后把它删除。再遍历图，把这个点作为起点的边 (其他点邻接表的元素) 删除，直到图为空返回 true 或者找不到这个点，返回 false。java ac 代码：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 邻接表，存放的是指向该节点的其他节点编号，而不是边
// 如果某个点没有其他点指向它，那么对应的 list 为空。
HashMap<Integer,List<Integer>> map = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++)
map.put(i,new ArrayList());
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
List<Integer>list = map.get(latter);
list.add(previous);
}
while(map.size() > 0)
{
// 判断是否能找到一个没有任何节点指向的节点
boolean flag = false;
int num = 0;
for(Map.Entry<Integer,List<Integer>> entry:map.entrySet())
if(entry.getValue().size() == 0)
{
flag = true;
num = entry.getKey();
break;
}
if(!flag)return false;
map.remove(num);
Iterator<List<Integer>> it = map.values().iterator();
while(it.hasNext())
it.next().remove(new Integer(num));
}
return true;
}
}
下面这种是利用一个队列暂存入度为 0 的点的快速拓扑排序方法。因为它不必每次都从头查找入度为 0 的点，因此时间效率得到了提示。java ac 代码：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 邻接表, 表示法
HashMap<Integer,List<Integer>> map = new HashMap(numCourses);
// 存放每个点的入度，初始为 0
HashMap<Integer,Integer>map2 = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++){
map.put(i,new ArrayList());
map2.put(i,0);
}
// 构造邻接表，并求出每个点的初始入度。
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
List<Integer>list = map.get(previous);
list.add(latter);
map.put(previous,list);
map2.put(latter,map2.get(latter)+1);
}
// 暂存入度为 0 的节点。
ArrayDeque<Integer>queue = new ArrayDeque();
for(int i = 0;i < numCourses;i++)
if(map2.get(i) == 0)
queue.offer(i);
// 统计最终能有多少个入度为 0 的点，若该数量小于 numCourses 则代表有环
int count = 0;
while(!queue.isEmpty())
{
int node = queue.poll();
for(int i:map.get(node))
{
int ii = map2.get(i);
ii -= 1;
if(ii != 0)
map2.put(i,ii);
// 这个点的入度变为了 0，可以加入队列中
else
queue.offer(i);
}
count++;
}
return count == numCourses;
}
}
