问题1727--DFS时间戳

1727: DFS时间戳

时间限制: 1 Sec  内存限制: 128 MB
提交: 18  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

请基于以下需求编写一个程序，对给定的有向图G＝(V，E)从1号点进行深度优先搜索，
并显示其执行过程。

  1. G以邻接表的形式给出。各顶点编号为1至n

  2. 各邻接表的顶点编号按升序排列

  3. 程序报告各顶点的发现时刻和结束时刻

  4. 深度优先搜索过程中，如果同时出现多个待访问的顶点，则选择其中最小的一个进行访问

  5. 首个被访问顶点的开始时刻为1


输入

第1行输入G的顶点数n。
接下来n行按如下格式输入各顶点a的邻接表。
u k v1 v2....vk
u为顶点编号 k为u的出度，v1 v2....vk为与u相邻点的顶点编号。

输出

输出按顶点编号顺序输出各顶点的id、d、f，每个顶点占1行，id、d、f之间用空格隔
开。id为顶点编号，d为该顶点的发现时刻，f为该顶点的结束时刻。
限制1≤n≤100

样例输入

6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

样例输出

1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6

来源/分类

深度优先搜索 

[提交] [状态]