题目地址：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; }}