网站需备案高清网站推广免费下载

reference way：在图里面能延伸的越远，deep越大，说明它能从自己延伸很长到别的节点（别的节点一定有入度），它越可能没有入度。

way：感觉和DFS1差不多，只是从远变成了多。

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;class Node
{
public:int label;vector<Node *> neighbors;Node(){}Node(int x){label=x;}
};class Record
{
public:Node* node;long childs;Record(Node* n, long num){node=n;childs=num;}
};Record* getRecord(Node *cur, map<Node *,Record *>&mp)
{if(mp.count(cur)) return mp[cur];long follow=0;for(auto next: cur->neighbors){follow += getRecord(next, mp)->childs;}Record *p=new Record(cur,follow+1);mp[cur]=p;return p;
}bool comp(Record *a, Record*b)
{return (a->childs)>(b->childs);
}vector<Node*> topoSort(vector<Node*>graph)
{//获取所有节点的deep然后 map[Node*]=Record*;map<Node*, Record*>mp;for(auto node: graph){getRecord(node, mp);}//将Record*们放到vec中准备排序vector<Record*>vec;for(auto pa: mp){vec.push_back(pa.second);}sort(vec.begin(),vec.end(),comp);//放到答案数组中vector<Node*>result;for(auto m: vec){result.push_back(m->node);}return result;
}

和前一篇（图的拓扑序列（DFS1)-CSDN博客）对比着看。