会编程的土豆 • 计科学习者 个人主页 点击访问我的主页 核心专栏1 数据结构与算法 核心专栏2 LeetCode Hot 100✨ 面包会有的牛奶会有的一切都会有的1#includeiostream#includevector#includequeueusingnamespacestd;classSolution{public:boolcanFinish(intnumCourses,vectorvectorintprerequisites){vectorvectorintgraph(numCourses);vectorintindegree(numCourses,0);for(inti0;iprerequisites.size();i){intaprerequisites[i][0];intbprerequisites[i][1];graph[b].push_back(a);indegree[a];}queueintq;for(inti0;inumCourses;i){if(indegree[i]0){q.push(i);}}intlearned0;while(!q.empty()){intcourseq.front();q.pop();learned;for(inti0;igraph[course].size();i){intnextgraph[course][i];indegree[next]--;if(indegree[next]0){q.push(next);}}}returnlearnednumCourses;}};这个题是这样一个逻辑首先看题目就是一个很经典的拓扑排序他不是说一个课程完成之后才能进行下一个吗这种就是很典型的拓扑排序这种只需要判断是否有环就行了为什么要判断有没有环因为有环的话他那个环的indegree就都是1了如果是1的话就无法进入队列队列里的值表示的是可以直接修的课无须其他课程先修完当做条件所以最后才有个把这个课修完的话这个课的下一个课就直接indegree–修完一门课learned一下然后删掉这门课有环的话环上的课是不可能到indegree0的所以有环的话课删除掉的也就是learened掉的肯定是小于numcourses的**2**#includevector#includequeueusingnamespacestd;classSolution{public:vectorintfindOrder(intnumCourses,vectorvectorintprerequisites){// 1. 建图vectorvectorintgraph(numCourses);vectorintindegree(numCourses,0);for(autoprereq:prerequisites){intaiprereq[0];// 要学的课intbiprereq[1];// 先修课graph[bi].push_back(ai);// bi → aiindegree[ai];// ai 的入度1}// 2. 初始化队列入度为0的课可以直接学queueintq;for(inti0;inumCourses;i){if(indegree[i]0){q.push(i);}}// 3. 拓扑排序记录顺序vectorintorder;while(!q.empty()){intcourseq.front();q.pop();order.push_back(course);// ← 关键记录学完的课for(intnext:graph[course]){indegree[next]--;if(indegree[next]0){q.push(next);}}}// 4. 判断是否有环if(order.size()!numCourses){return{};// 有环返回空数组}returnorder;}};这个和上一题非常相似只不过多了个让输出顺序无须大惊小怪只需要建立一个动态数组order把每次pop掉的课加进order数组即可为什么呢因为他这个队列就是按照顺序的必须indegree为0了才能加入队列加入进队列的都是按序列的最后只需要判断有没有环有环就是没有办法修完课直接返回空否则返回order数组