天津建设厅 注册中心网站首页今日头条新闻军事

思路：拓补排序

其实就是对于第一个题的问题变了一个问法，上一个题本质上是求有没有环，这道题本质上就是让你求出来符合没有环的路径输出而已，本质上没有什么区别。

不同就在于这里需要你额外开一个数组用来存储你遍历这个有向图的路径。

注意：并不是说存储返回就完事了，因为所给的数据有可能是不构成拓补排序的要求的，我们需要判断一下这个图是不是有向无环图，如果是，那么拓补排序是可以的；不是的话，我们在存储路径的时候会重复一个环的点，导致输出错误。

这里的判断有没有环其实就是用一个计数器判断是不是符合全部点都遍历，不出现重复的情况下。

上代码：

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>>s(numCourses);vector<int>counts(numCourses,0);for(int i=0;i<prerequisites.size();i++){s[prerequisites[i][1]].push_back(prerequisites[i][0]);counts[prerequisites[i][0]]++;}queue<int>q;vector<int>res;int cnt=0;for(int i=0;i<numCourses;i++){if(counts[i]==0){q.push(i);res.push_back(i);}}while(!q.empty()){int tmp=q.front();q.pop();++cnt;for(int i:s[tmp]){if(--counts[i]==0){q.push(i);res.push_back(i);}}}if(cnt==numCourses){return res;}else{return {};}}
};