开发公司出纳收款制度,厦门seo网站优化,杭州seo博客有哪些,wordpress解析插件题目链接#xff1a;http://bailian.openjudge.cn/practice/4084/ 总时间限制: 1000ms 内存限制: 65536kB描述给出一个图的结构#xff0c;输出其拓扑排序序列#xff0c;要求在同等条件下#xff0c;编号小的顶点在前。 输入若干行整数#xff0c;第一行有2个数#xff…题目链接http://bailian.openjudge.cn/practice/4084/ 总时间限制: 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 这道题可以考虑使用优先队列。下面的代码偷懒直接使用最简单粗暴的方法 1 #includestdio.h2 #includeiostream3 #includestdlib.h4 #includestring.h5 #includealgorithm6 using namespace std;7 8 #define maxN 10009 #define maxM 2000
10
11 struct NODE
12 {
13 int from; //边的起点
14 int to; //边的终点
15 };
16 struct NODE edge[maxM]; //边数组
17 int head[maxN]; //存储出发点为 Vi 的第一条边在 edge[ ]中的位置一般初始化为-1。
18
19 int n,m;//n个点m条边的图
20 int indegree[maxN];
21 int ttt;
22
23 bool cmp(NODE a,NODE b)
24 {
25 if(a.fromb.from)return a.tob.to;
26 return a.fromb.from;
27 }
28 void topo_sort();//利用队列完成无前驱节点优先的拓扑排序. 编号小的节点优先输出.
29 int main(int argc, char *argv[])
30 {
31 int i;
32
33
34 scanf(%d%d,n,m);
35 for(i0;im;i) cinedge[i].fromedge[i].to;
36 sort(edge,edgem,cmp);
37 //for(i0;im;i) printf(%d %d\n,edge[i].from,edge[i].to);//测试代码
38 memset(head,-1,sizeof(head));
39 head[edge[0].from]0;
40 indegree[edge[0].to]1;
41 for(i1;im;i)
42 {
43 if(edge[i].from ! edge[i-1].from)
44 {
45 head[edge[i].from]i;//标记以第 i 个点做起点的第一条边在 edge[]的位置
46 }
47 indegree[edge[i].to];//记录各个顶点的入度
48 }
49 //for(i1;in;i) printf(%d ,indegree[i]); printf(\n); //测试代码输出各个点的入度.(题目数据顶点编号从1开始
50
51 topo_sort();
52
53 return 0;
54 }
55
56 void topo_sort()//利用队列完成无前驱节点优先的拓扑排序. 编号小的节点优先输出.
57 {
58 int i,k;
59 tttn;
60 while(ttt0)
61 {
62 for(i1;in;i)//扫描寻找编号最小的无前驱节点
63 {
64 if(indegree[i]0)
65 {
66 printf(v%d ,i);
67 ttt--;
68 if(head[i]!-1)//该顶点有邻接点
69 {
70 //遍历该顶点出发的全部有向边,把这些边的终点的入度减1.
71 for(khead[i];edge[k].fromikm;k)
72 {
73 indegree[edge[k].to]--;
74 }
75 head[i]-1;//删除该顶点出发的全部有向边
76 }
77 indegree[i]-1;
78 break;
79 }
80 }
81 }
82 } 转载于:https://www.cnblogs.com/huashanqingzhu/p/9291886.html
