题面

深度优先搜索（DFS）是一种基于尽可能多地访问相邻顶点策略的图搜索算法。如果顶点 v 有未搜索的顶点则递归搜索直至 v 的最后一条边。在搜索了 v 的所有边之后，搜索继续返回到找到 v 时经过的边。

搜索从原来的起点开始，直到找到所有可达的顶点，如果有未发现的顶点，则以编号最小的顶点作为新的起点继续搜索。

深度优先搜索使用以下时间戳标记每个顶点：
d[v]：记录第一次发现v时的时间。
f[v]：记录v的邻接表被检查完成时的时间。

编写一个程序，显示基于以下规则的给定有向图 G = (V, E) 的深度优先搜索相关信息：

其中图 G 以邻接表的形式给出。每个顶点从 1 到 n 编号。
每个邻接表的顶点按编号升序排列。
程序需要输出每个顶点的发现和完成时间。
备注：
在DFS的过程中，如果要访问的顶点有多个，则选择顶点数最小的那个。
设 1 为第一个要访问的顶点的开始时间。

输入

第一行给出了 G 中的顶点数 n。
接下来的 n 行给出了每个顶点 u 的邻接表，格式如下：
ukv1​v2​…vk​
u 是顶点的编号，k 是 u 的度数，v1​v2​…vk​ 是与 u 相邻的顶点的编号。

输出

输出 n 行，在第 i 行上输出第 i 个顶点的 id、d、f以空格分隔。
id是顶点的编号，d是顶点的发现时间，f是顶点的完成时间。
按顶点编号从小到大输出。

约束

• 1≤n≤100

输入样例

4
1 1 2
2 1 4
3 0
4 1 3

输出样例

1 1 8
2 2 7
3 4 5
4 3 6 

代码 

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stack>
using namespace std;vector<int> discovery;
vector<int> finish;
vector<bool> visited;
int timee=1;
void dfs(int u,const vector<vector<int> >& adj)
{discovery[u]=timee++;visited[u]=true;for(int i=0;i<adj[u].size();i++){int v=adj[u][i];{if(!visited[v]){dfs(v,adj);}}}finish[u]=timee++;
}
int main() {int n;cin >> n;vector<vector<int>> adj(n);for(int i=0;i<n;i++){int u,k;cin>>u>>k;u--;for(int j=0;j<k;j++){int v;cin>>v;v--;adj[u].push_back(v);}sort(adj[u].begin(),adj[u].end());}// 初始化数据结构discovery.assign(n, -1);finish.assign(n, -1);visited.assign(n, false);// 对每个未访问的节点执行DFSfor (int i = 0; i < n; ++i) {if (!visited[i]) {dfs(i, adj);}}for(int i=0;i<n;i++){cout << (i + 1) << " " << discovery[i] << " " << finish[i] << endl;}return 0;
}