力扣 hot100 Day55

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

//抄的class Solution {public: bool canFinish(int numCourses, vector<vector>& prerequisites) { vector<vector> adj(numCourses); vector inDegree(numCourses,0); for(auto& edge:prerequisites) { adj[edge[1]].push_back(edge[0]); inDegree[edge[0]]++; } queue q; for(int i=0;i<numCourses;i++) { if(inDegree[i]==0) { q.push(i); } } int learned = 0; while(!q.empty()) { int u = q.front(); q.pop(); learned++; for(int i:adj[u]) { if(--inDegree[i]==0) {  q.push(i); } } } return learned == numCourses; }};

首先构建邻接表和入度数组，入度即指向每个课程的前置课程数，入度为零，表示可以直接学习

逻辑很清晰，首先将所有入度为零的课程入队，出队时，出队的课程指向的课程入度减一，如果变化后入度等于零则入队，这样循环到底，直至队列清空。

循环时记录学习数可以方便最后判断，也可以判断是否还有课程入度为零，多一次循环少一个变量