Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531646211000,"title":"Uva 10305 - Ordering Tasks 队列 和dfs实现","dislikeCnt":2,"content":"**我太菜了!!!**\n\n```\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003cqueue\u003e\nusing namespace std;\nint n,m;\nint degree[105],road[105][105],topo[105];//road记录有向路径,topo记录排序后的结果 \nvoid tp(){ //degree记录连接到i点的路径数 \n\tqueue\u003cint\u003eq; \n\tint tot\u003d1;//初始化 \n\tfor(int i\u003d1;i\u003c\u003dn;i++) //记录起点 \n\t\tif(!degree[i])q.push(i);\n\twhile(!q.empty()){\n\t\tint head\u003dq.front();//记录已排列的点 \n\t\tq.pop();//出队 \n\t\ttopo[tot++]\u003dhead;//得到第一个结果 \n\t\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\t\tif(road[head][i])//拓展到能到达的点 \n\t\t\t\tif(!(--degree[i]))//若已经没有路径可以到达该点,则该点成为新起点 \n\t\t\t\t\tq.push(i);\n\t}\n\tprintf(\"%d\",topo[1]);//给空格腾位。。。 \n\tfor(int i\u003d2;i\u003ctot;i++)\n\t\tprintf(\" %d\",topo[i]);\n\tprintf(\"\\n\");\n}\nint main() {\n\twhile(scanf(\"%d%d\",\u0026n,\u0026m)\u0026\u0026(n||m)){\n\t\tmemset(road,0,sizeof(road));\n\t\tmemset(degree,0,sizeof(degree));\n\t\tint a,b;\n\t\tfor(int i\u003d1;i\u003c\u003dm;i++){\n\t\t\tscanf(\"%d%d\",\u0026a,\u0026b);\n\t\t\troad[a][b]\u003d1;//记录一条由a指向b的路径 \n\t\t\tdegree[b]++;//能到达b点的路径数+1 \n\t\t}\n\t\ttp();//排出拓扑序并输出 \n\t}\n\treturn 0;\n}\n\n```\n补一个模拟队列\n```\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003ciostream\u003e\nusing namespace std;\nint road[105][105],id[105],tp[105],n,m,head,tail,tot;\nint main(){\n\twhile(scanf(\"%d%d\",\u0026n,\u0026m)\u0026\u0026(n||m)){\n\t\tmemset(road,0,sizeof(road));\n\t\tmemset(id,0,sizeof(id));\n\t\thead\u003dtail\u003d0;\n\t\tfor(int i\u003d0;i\u003cm;i++){\n int a,b;\n\t\t\tscanf(\"%d%d\", \u0026a, \u0026b);\n\t\t\troad[a][b] \u003d 1;\n\t\t\tid[b]++;\n\t\t}\n\t\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\t\tif(!id[i])\n\t\t\t\ttp[tail++]\u003di;\n\t\twhile(tail!\u003dhead) {\n\t\t\ttot\u003dtp[head++];\n\t\t\tif(head\u003d\u003d1)printf(\"%d\",tot);\n\t\t\telse printf(\" %d\",tot);\n\t\t\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\t\t\tif (road[tot][i])\n\t\t\t\t\tif (!(--id[i]))\n\t\t\t\t\t\ttp[tail++] \u003d i;\n\t\t}\n\t\tprintf(\"\\n\");\n\t}\n\treturn 0;\n}\n```","threadId":31547,"likeCnt":1,"createTime":1531644132000,"isWorkbook":false,"viewCnt":2212,"openness":2,"fav":false,"id":522,"trustable":false}