力扣 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<int>>& prerequisites) {vector<vector<int>> adj(numCourses);vector<int> inDegree(numCourses,0);for(auto& edge:prerequisites){adj[edge[1]].push_back(edge[0]);inDegree[edge[0]]++;}queue<int> 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;}
};

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

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

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