Pro.ID1333 Title图的深度优先遍历 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1333 AC517 Submit3002 Ratio17.22% 时间&空间限制描述编号为1…N 的N个城市之间以单向路连接,每一条道路的长度都是一样的。。。。有点不可思议。。。。 从城市1出发,进行深度优先遍历,请输出遍历的序列。对一个顶点的若干邻接顶点,优先遍历号码大的邻接顶点。 输入测试用例的第一行包含两个整数,分别是 N、R : N:表示城市的总数,2 ≤ N ≤ 100 R:表示道路的条数,1 ≤ R ≤ 10000 接下来的R行,每行用 S D(以空格隔开)表示一条道路: S:表示道路的出发城市,1 ≤ S ≤ N D:表示道路的目标城市,1 ≤ D ≤ N 输出Description 编号为1…N 的N个城市之间以单向路连接,每一条道路的长度都是一样的。。。。有点不可思议。。。。 从城市1出发,进行深度优先遍历,请输出遍历的序列。对一个顶点的若干邻接顶点,优先遍历号码大的邻接顶点。 Input 测试用例的第一行包含两个整数,分别是 N、R : N:表示城市的总数,2 ≤ N ≤ 100 R:表示道路的条数,1 ≤ R ≤ 10000 接下来的R行,每行用 S D(以空格隔开)表示一条道路: S:表示道路的出发城市,1 ≤ S ≤ N D:表示道路的目标城市,1 ≤ D ≤ N Output 输出一行结果:深度优先遍历的城市序列。每个城市编号后跟一个空格。 Sample Input 6 7 Sample Output 1 3 5 4 6 2 Hint 在本题,用邻接矩阵来存储图,实现"查找第一个邻接顶点"、"找下一个邻接顶点"比较简单。注意,这并不意味着邻接表在任何时候都不好用,例如在顶点很多的情况下,邻接矩阵就存储不下,只能用邻接表。 Author 样例输入6 7 样例输出1 3 5 4 6 2 提示在本题,用邻接矩阵来存储图,实现"查找第一个邻接顶点"、"找下一个邻接顶点"比较简单。注意,这并不意味着邻接表在任何时候都不好用,例如在顶点很多的情况下,邻接矩阵就存储不下,只能用邻接表。 作者 |