网站建设中英文,深圳建设工程价格信息网站,wordpress输出响应式图片,建设个读书网站大约需要投入多少钱拓扑排序 一.定义 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序#xff0c;是将G中所有顶点排成一个线性序列#xff0c;使得图中任意一对顶点u和v#xff0c;若u#xff0c;v ∈E(G)#xff0c;则u在线性序列中出现在v之前。 通常#xff0c;… 拓扑排序 一.定义 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序是将G中所有顶点排成一个线性序列使得图中任意一对顶点u和v若uv ∈E(G)则u在线性序列中出现在v之前。 通常这样的线性序列称为满足拓扑次序(Topological Order)的序列简称拓扑序列。 注意: 1)只有有向无环图才存在拓扑序列; 2)对于一个DAG,可能存在多个拓扑序列此题已经规定了数字的优先级所以答案唯一; 二.拓扑序列算法思想 (1)从有向图中选取一个没有前驱(即入度为0)的顶点并输出之; (2)从有向图中删去此顶点以及所有以它为尾的弧; 重复上述两步直至图空或者图不空但找不到无前驱的顶点为止。 #include iostream
#include cstdio
#include cstring
#include vector
#include queue
#includefunctional
#define MAXSIZE 100005
using namespace std;vectorintG[MAXSIZE];
priority_queueint ,vectorint, lessint q;
int in[MAXSIZE];int main()
{int T,n,m,a,b;scanf(%d,T);while(T--){memset(in,0,sizeof(in));vectorint ans;for(int i0;iMAXSIZE;i)G[i].clear();scanf(%d%d,n,m);while(m--){scanf(%d%d,a,b);in[a];G[b].push_back(a);}for(int i1;in;i)if(!in[i]) q.push(i);while(!q.empty()){int uq.top();ans.push_back(u);q.pop();int lenG[u].size();for(int i0;ilen;i){int vG[u][i];in[v]--;if(!in[v])q.push(v);}}int lenans.size();for(int ilen-1;i0;i--)printf(%d%c,ans[i],i0?\n: );}return 0;
} View Code 转载于:https://www.cnblogs.com/alan-W/p/6640008.html
