1.题目描述

2.思路

记录每门课程的前置课程数量，记录每门课程是哪些课程的前置课程。
（1）如果有向图中的拓扑图中存在环，则说明所有的课程是无法完成的。
（2）使用拓扑排序，在图中每个节点的入度和出度。
（3）统计完每个节点的入度，使用广度优先搜索。因为入度为0，说明没有先修课程，也就是先修课程已经完成了。如果c1已经修完，C3和C8以C1为先修课程，所以入度就可以-1.
将入度为0的课程加入到待学习的课程中。
最后要判断优秀，已学习的课程的数量是否等于输入课程的数量。

补充：


补充2：

3.代码实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class H207 {List<List<Integer>> edges;//邻接表，edges[i] 存储从节点 i 指向的所有节点// 入度数组，indeg[i] 表示课程 i 被依赖的次数int[] indeg;public boolean canFinish(int numCourses, int[][] prerequisites) {edges=new ArrayList<List<Integer>>();//声明edges的变量
//        创建一个 ArrayList，每个元素是一个 List<Integer>。
//
//        它表示图中每个节点的邻接列表（即当前节点能指向哪些其他节点）。
//
//        初始状态：edges = []for(int i=0;i<numCourses;i++){edges.add(new ArrayList<Integer>());//        edges = [
//    [],  // 课程 0 的邻接列表
//    [],  // 课程 1 的邻接列表
//    []   // 课程 2 的邻接列表
//]}//初始化入度数组，初始化所有课程的入度为0indeg=new int[numCourses];//构建图的邻接表和计算入度数组for(int[] info:prerequisites){edges.get(info[1]).add(info[0]);//课程info[1]->课程info[0]++indeg[info[0]];//课程info[0]的入度+1}//创建一个队列，用于存放所有入度为0的课程（及时没有依赖的课程）Queue<Integer> que=new LinkedList<Integer>();for(int i=0;i<numCourses;++i){if(indeg[i]==0){que.offer(i);//将所有入度为0的课程加入队列}}//记录已访问（已学习）的课程数量int visited=0;//bfs拓扑排序while(!que.isEmpty()){++visited;//每学习一门课程，已访问的课程数量+1int u=que.poll();//从队列中取出一门可以学习的课程 ufor(int v:edges.get(u)){--indeg[v];//学完课程u后，v的入度-1if(indeg[v]==0){//如果v的入度变为0，说明没有其他前置课程可以学习que.offer(v);//将课程v加入到队列}}}//判断是否所有课程都能学完//如果已访问的课程数量等于总课程数量，说明没有环，能完成所有课程return visited==numCourses;}
}