著名的王牌间谍 007 需要执行一次任务获取敌方的机密情报。已知情报藏在一个地下迷宫里迷宫只有一个入口里面有很多条通路每条路通向一扇门。每一扇门背后或者是一个房间或者又有很多条路同样是每条路通向一扇门…… 他的手里有一张表格是其他间谍帮他收集到的情报他们记下了每扇门的编号以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。内线告诉他情报就藏在迷宫的最深处。但是这个迷宫
这段程序的设计思路是使用拓扑排序的方法找出距离入口最远的那扇门。
首先,定义了一个整型数组degree,用来记录每扇门的入度(即有多少条通路通向该门)。 然后,定义了一个vector数组v,用来记录每扇门背后的通路所到达的门的编号。 接着,定义了一个队列q,用来进行广度优先搜索。
程序中的主要逻辑如下:
- 读入输入的迷宫信息,包括每扇门的编号和通路到达的门的编号,并在degree和v数组中记录相应的信息。
- 初始化变量x为1,表示起始门的编号。
- 遍历所有门,找到入度为0的门,将其编号赋给x。
- 将x入队列q。
- 当队列q非空时,依次取出队首元素x,并将x的所有通路所到达的门的编号入队列q。
- 最终,x的值即为距离入口最远的那扇门的编号。
这段程序没有涉及文件操作和数据库操作,只是从标准输入中读取数据并输出结果。
原文地址: http://www.cveoy.top/t/topic/iR0g 著作权归作者所有。请勿转载和采集!