【力扣每日一题】2023.9.10 课程表Ⅱ

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

今天的题目和昨天类似，不过今天要我们求出学习所有课程的先后顺序。

昨天只需要我们求出能否学习完所有课程，因此我们只需要判断构建出的有向图中是否有环即可，而今天的题我们就不能简单判断有没有环了。

要返回学习课程的先后顺序，最简单最直接的方法就是模拟。

我们跟昨天一样，首先先把有向图构建出，接着我们再模拟学习，模拟之前我们还需要拿一个数组来存放学习课程的顺序，以及一个set来记录学过的课程，其实数组和set里的元素是一致的，不过set更方便统计set中是否含有某个元素。

每次学习我们都把所有课程遍历一遍，如果课程我们没有学过（不在set里），我们就遍历这门课程的先修课程，如果它的先修课程全部都在set中，那么我们本轮学习就可以学这门课程，把它添加进答案数组以及set中。

课程遍历完毕之后，我们还需要做一个判断，如果本轮学习没有学习到任何课程，那么就表示我们无法学习到所有的课程（图中有环），返回空数组即可。

一直重复上述模拟学习的过程，直到答案数组的长度等于课程数目了，就表示我们学习完了所有的课程，这时退出循环，返回答案数组即可。

代码：

class Solution {
public:unordered_map<int,vector<int>>m;vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {for(auto& p:prerequisites){         //构建有向图 if(m.find(p[0])==m.end()) m[p[0]]=vector<int>(0);m[p[0]].push_back(p[1]);}vector<int>res;     unordered_set<int>s;    //用于统计已经学习的课程int last=0;             //记录上一轮的学习课程数while(res.size()!=numCourses){for(int i=0;i<numCourses;i++){      //遍历所有课程  if(s.count(i)==0){              //如果没学过课程那么进入判断bool flag=true;for(int c:m[i]){           if(s.count(c)==0){flag=false;break;}}if(flag){                   //如果本课程的所有先修课都学过,那么添加进答案res.push_back(i);s.insert(i);}}}//如果本轮学习过后,学习课程和上一轮一样,那么我们无法学完所有课程,返回空if(last==res.size()) return vector<int>(0);last=res.size();}return res;}
};