【算法练习】数据结构/图论 poj4084:拓扑排序

题目链接http://bailian.openjudge.cn/practice/40844084:拓扑排序总时间限制:1000ms内存限制:65536kB描述给出一个图的结构输出其拓扑排序序列要求在同等条件下编号小的顶点在前。输入若干行整数第一行有2个数分别为顶点数v和弧数a接下来有a行每一行有2个数分别是该条弧所关联的两个顶点编号。v100, a500输出若干个空格隔开的顶点构成的序列(用小写字母)。样例输入6 8 1 2 1 3 1 4 3 2 3 5 4 5 6 4 6 5样例输出v1 v3 v2 v6 v4 v5题目意思就是有向图的拓扑排序维护一个队列保存入度为0的结点题目又要求说编号小的顶点在前于是这个队列可以定义成优先队列也就是最小堆默认的是最大堆priority_queueint,vectorint,greaterint Q;快乐AC,记住思路是很简单的模板题AC://图论 拓扑排序 #include iostream #include queue #include vector using namespace std; priority_queueint,vectorint,greaterint Q; int inDegree[120]; //代表顶点的入度 vectorint G[120]; int main(){ int v,a; //初始化 for(int i0;i120;i){ inDegree[i]0; G[i].clear(); //清空vector中的元素 } cinva; int x,y; for(int i0;ia;i){ cinxy; inDegree[y]; G[x].push_back(y); } for(int i1;iv;i){ if(inDegree[i]0) Q.push(i); } while (!Q.empty()){ int curQ.top(); Q.pop(); coutvcur ; for(int i0;iG[cur].size();i){ int uG[cur][i]; inDegree[u]--; if(inDegree[u]0){ Q.push(u); } } } coutendl; return 0; }