网站上线步骤 icp备案,临沂做网站公司哪家好,浅谈电子商务网站的建设与管理,注册网站对接的短信平台题目来源#xff1a;117. 软件构建 C题解#xff08;来源代码随想录#xff09;#xff1a;拓扑排序#xff1a;给出一个 有向图#xff0c;把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法。
拓扑排序的过程#xff0c;其实就两步#xff1…题目来源117. 软件构建 C题解来源代码随想录拓扑排序给出一个 有向图把这个有向图转成线性的排序。拓扑排序也是图论中判断有向无环图的常用方法。
拓扑排序的过程其实就两步
找到入度为0 的节点加入结果集将该节点从图中移除
循环以上两步直到 所有节点都在图中被移除了。
#include iostream
#include vector
#include queue
#include unordered_map
using namespace std;
int main() {int m, n, s, t;cin n m;vectorint inDegree(n, 0); // 记录每个文件的入度unordered_mapint, vectorint umap;// 记录文件依赖关系vectorint result; // 记录结果while (m--) {// s-t先有s才能有tcin s t;inDegree[t]; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queueint que;for (int i 0; i n; i) {// 入度为0的文件可以作为开头先加入队列if (inDegree[i] 0) que.push(i);//cout inDegree[i] endl;}// int count 0;while (que.size()) {int cur que.front(); // 当前选中的文件que.pop();//count;result.push_back(cur);vectorint files umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i 0; i files.size(); i) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] 0) que.push(files[i]);}}}if (result.size() n) {for (int i 0; i n - 1; i) cout result[i] ;cout result[n - 1];} else cout -1 endl;}
