课程表
题目链接：https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-100-liked
我的解答：
无分析：一开始想到用哈希表，但提交后发现有key重复的样例，行不通，然后就没什么思路了。
看了官方题解后的解答：
//方法一：拓扑排序+深度优先搜索 //时间复杂度：O(n+m)，n为课程数（图的节点个数），m为先修课程的要求数（图中边的条数） //空间复杂度：O(n+m)，n为课程数（图的节点个数），m为先修课程的要求数（图中边的条数） List<List<Integer>> edges;//存储有向图 int[] status;//存储每个节点的状态（0：未搜索，1：搜索中，2：搜索完成） boolean valid;//判断图中是否存在环，不存在为true，存在为false public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<>(numCourses); for(int i=0; i<numCourses; i++){ edges.add(new ArrayList<>()); } status = new int[numCourses]; valid = true; //构建有向图 for(int[] info : prerequisites){ edges.get(info[1]).add(info[0]); } //每次挑选一个「未搜索」的节点，开始进行深度优先搜索 for(int i=0; i<numCourses && valid; i++){ if(status[i] == 0){ dfs(i); } } if(!valid){ return false; } //如果没有环，那么就有拓扑排序 return true; } public void dfs(int cur){ status[cur] = 1;//标记此节点为 [搜索中] //搜索cur的相邻的节点 //只要发现有环，立刻停止搜索 for(int neighbor : edges.get(cur)){ if(status[neighbor] == 0){//若为未搜索的节点，则搜索相邻节点 dfs(neighbor); } else if(status[neighbor] == 1){//若为搜索中的节点，则说明找到了环 valid = false; } if(!valid){ return; } } status[cur] = 2;//将cur标记为搜索完成 } //方法二：拓扑排序+广度优先搜索 //时间复杂度：O(n+m)，n为课程数（图的节点个数），m为先修课程的要求数（图中边的条数） //空间复杂度：O(n+m)，n为课程数（图的节点个数），m为先修课程的要求数（图中边的条数） List<List<Integer>> edges;//存储有向图 int[] indeg;//存储每个节点的入度，入度为0说明当前课程的前置条件都已满足了，可以学习当前课程了 int count;//记录入度为0的节点个数 public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<>(); for(int i=0; i<numCourses; i++){ edges.add(new ArrayList<>()); } indeg = new int[numCourses]; count = 0; //构建有向图，并初始化每个节点的入度信息 for(int[] info : prerequisites){ edges.get(info[1]).add(info[0]); indeg[info[0]]++; } Queue<Integer> queue = new LinkedList<>(); //将入度为0的节点入队 for(int i=0; i<numCourses; i++){ if(indeg[i] == 0){ queue.offer(i); } } while(!queue.isEmpty()){ //从队首取出一个节点 int cur = queue.poll(); count++; //将cur相邻节点的入度减一 for(int neighbor : edges.get(cur)){ indeg[neighbor]--; //若相邻节点的入度变为0，则将其入队 if(indeg[neighbor] == 0){ queue.offer(neighbor); } } } //存在入度不为0的节点，说明图存在环 return count == numCourses; }分析：
1、本题的本质就是判断有向图是否存在拓扑排序。
2、拓扑排序的定义：给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面。那么称该排列是图 G 的「拓扑排序」。
3、方法一的解题思路：构建有向图edges（边u—>v： u是v的前置条件，即想要完成v，必须先完成u），通过记录每个节点的状态（未搜索、搜索中、搜索完成），判断图中是否存在环（若深搜过程中搜索到状态为搜索中的节点，说明图中存在环）。每次选取一个状态为未搜索的节点进行深搜，先将当前节点的状态更新为搜索中，然后搜索当前节点的相邻节点，若搜索过程中没有出现环，且当前节点的相邻节点都已经搜索完成，则将当前节点的状态更新为搜索完成即可；若搜索过程中出现环，则直接停止搜索并返回false。
4、方法二的解题思路：构建有向图edges（边u—>v： u是v的前置条件，即想要完成v，必须先完成u），根据每个节点的入度判断当前节点是否可以进行学习，入度为0则说明当前节点的前置条件都已经完成，可以学习该节点了。用队列存储每个入度为0的节点，每次出队一个节点，然后将出队节点的相邻节点的入度减一，若出现入度为0的节点，将其入队，在此过程中统计出队的节点个数（即可以完成学习的课程数），重复以上操作直到队列为空。若最后统计得到的出队节点数与课程总数不相等，则说明图中存在环，无法完成所有课程的学习，反之则说明能完成所有课程的学习。
总结
- 本题主要考察有向图的构建和拓扑排序的相关知识，关键在于如何判断一个有向图中是否存在拓扑排序。
- 本题与https://leetcode.cn/problems/course-schedule-ii/solutions/249149/ke-cheng-biao-ii-by-leetcode-solution/几乎是一样的题目，唯一的区别在于本题只需判断有向图中是否存在拓扑排序，而链接给出的题还需要我们获取一种拓扑排序。而关于拓扑排序的相关知识可以参考所给链接的题解。
